[LeetCode] 735. Asteroid Collision

行星碰撞。

题意是给一个数组 asteroids，表示在同一行的行星。对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。找出碰撞后剩下的所有行星。

碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。例子，

Example 1:

Input:
asteroids = [5, 10, -5]
Output: [5, 10]
Explanation:
The 10 and -5 collide resulting in 10.  The 5 and 10 never collide.

Example 2:

Input:
asteroids = [8, -8]
Output: []
Explanation:
The 8 and -8 collide exploding each other.

Example 3:

Input:
asteroids = [10, 2, -5]
Output: [10]
Explanation:
The 2 and -5 collide resulting in -5.  The 10 and -5 collide resulting in 10.

Example 4:

Input:
asteroids = [-2, -1, 1, 2]
Output: [-2, -1, 1, 2]
Explanation:
The -2 and -1 are moving left, while the 1 and 2 are moving right.
Asteroids moving the same direction never meet, so no asteroids will meet each other.

思路是用stack做。先创建一个空的stack，一开始当stack为空的时候，直接就把数组里面的元素加进去；当stack不为空的时候，做如下判断

1. 先看一下栈顶元素的正负和要塞入的元素的正负。如果栈顶元素为负（往左）或者要塞入的元素为正（往右），说明加入栈的时候不会发生碰撞，直接就加了；

2. 除了第一种情况，其他情况就有可能会发生碰撞了。这时候判断如果栈顶元素 + 塞入元素 < 0说明两者会相向碰撞并且栈顶元素会被损毁，此时要pop出栈顶元素并且i--，看看试图加入栈的元素能否把新的栈顶元素（原来是在i - 1的位置上的元素）再次损毁

3. 如果两者相向碰撞但是速度一样，两者互相抵消，栈顶元素直接pop

时间O(n)

空间O(n)

 /**
  * @param {number[]} asteroids
  * @return {number[]}
  */
 var asteroidCollision = function (asteroids) {
     const stack = [];
     const len = asteroids.length;
     for (let i = 0; i < len; i++) {
         const cur = asteroids[i];
         // if stack is empty, just push
         if (!stack.length) {
             stack.push(cur);
         } else {
             // peek the stack top
             const pop = stack[stack.length - 1];
             if (pop < 0 || cur > 0) {
                 stack.push(cur);
             } else if (pop + cur < 0) {
                 stack.pop();
                 i--;
             } else if (pop + cur === 0) {
                 stack.pop();
             }
         }
     }
     return stack;
 };

巴特西

[LeetCode] 735. Asteroid Collision

最新文章

热门文章