Jianbo Dai's

lc735.行星碰撞

 
  • Sep 20, 2021

题目链接

这是一个栈的题目，我一开始做的时候一直试图套单调栈的模板，发现不太行，后来发现和单调栈的区别还是很大的，只是一个普通的栈，有一点点类似罢了。考虑以下这些情况：

首先，循环每一个元素时，在什么情况下无脑入栈呢？

  1. 栈为空
  2. 栈顶元素为负数(下一个为负数则一起向左，下一个为正数则分向两边)
  3. 当前元素为正数（栈顶为正一起向右，栈顶为负分向两边）

下来，我们需要看碰撞的场景又细分为什么情况：

  1. 栈顶元素大于abs(当前元素)，当前元素被撞毁
  2. 栈顶元素等于abs(当前元素)，栈顶弹出和当前元素抵消
  3. 栈顶元素小于abs(当前元素)，栈顶弹出，并与新栈顶完成上述判断

最终返回栈即可

这个算法的时间复杂度是O（N），空间复杂度是O（N）。

python:

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack = []
        for new in asteroids:
            while stack and (stack[-1] > 0 and new < 0):
                if stack[-1] > -new:
                    break
                elif stack[-1] < -new:
                    stack.pop()
                    continue
                else:
                    stack.pop()
                    break
            else:
                stack.append(new)
        return stack
Search