小白刷不停 735 ～ 行星相撞

基本信息

• 题号：735
• 题厂：lya
• 难度系数：中

数组 asteroid 代表一些行星，正数代表星星右行，负数代表星星左行……星星不能为 0。

如果两行星发生撞击，绝对值较小的撞没；如果绝对值相等，则 2 个一起被撞没……

例如：asteroids = [10,2,-5]，返回 [10]

2 ～ -5 发生相撞，-5 绝对值较大，2 被撞没；-5 继续前行和 10 发生相撞，10 绝对值较大，这次 -5 被撞没

解题思路

• 撞击 ～ 即在数组内部发生配对问题——此类问题一般采用 stack 先进后出原理解决。例如脸书著名 #20 括号判断问题，都是异曲同工的思路模型

• 分析相撞条件：只有前右行（正数）后左行（负数）的条件下才可能发生撞击

1. 当 stack 为空时，无论正数负数，都不会发生撞击
2. 当遇上正数时，是不会发生撞击的
3. 只有遇上负数，且 stack 最后一个元素为正时，撞击才会发生

• 检测撞击后，还需要进一步分析：

1. 相撞 2 星绝对值相等还是不相等；
2. 以及循环撞击问题。即 stack 被 pop 后下一个元素还为正时

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack = []
        
        for a in asteroids:
            while stack and a < 0 and stack[-1] > 0:
                diff = a + stack[-1]
                
                # 撞击发生后，我们通过重置 a = 0 解决达到当前行星绝对值较小或者相等的问题
                # 剩下的绝对值比较问题，则 stack 不断 pop 就好……
                if diff < 0:
                    stack.pop()
                elif diff > 0:
                    a = 0
                else:
                    a = 0
                    stack.pop()

            # 如果没有发生撞击，或者当前行星没有因为绝对值较小已经被撞没（重设 a = 0 了），还需要把 a 添加进 stack……     
            if a != 0:
                stack.append(a)
                    
        return stack

Constraints

• 2 <= asteroids.length <= 104
• -1000 <= asteroids[i] <= 1000
• asteroids[i] != 0

本题告知 「行星」不为 0；考试时可就此取值问题与考官讨论确认。

Big O

• Time：O（n）
• Space：O（n）， stack 引入

测试

• 相等行星相撞时
• 不等相撞时，发生循环相撞
• 不发生相撞时
• 因为不断相撞导致 stack 为空的情况
• ……

总结

• 如果熟悉 stack 原理及 stack 适合解决的套路问题，还是会比较容易想出解法
• 一旦想到需要引用 stack 解题，剩下的逻辑判断相对容易
• 但就各种撞击情况的判断问题，考察仔细思维严密性，以及解题后的各种测试分析