Leetcode 735. Asteroid Collision

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

**解析：**Version 1、Version 2，思路是一样的，写法不同。用栈实现，首先，判断当前小行星的直径，如果其大于0，或栈为空，或栈顶元素为负，则直接压入栈中，否则，则当前小行星的直径为负值，且栈顶元素为正值，然后对栈顶元素和当前小行星直径的绝对值比较，如果二者相等，则将当前小行星直径设为0，并将栈顶元素出栈，如果前者大于后者，不进行任何操作，处理下一个小行星直径，如果前者小于后者，则栈顶元素出栈，重复执行上述操作。

• Version 1

class Solution:def asteroidCollision(self, asteroids: List[int]) -> List[int]:stack = []for asteroid in asteroids:if asteroid > 0 or len(stack) == 0 or stack[-1] < 0:stack.append(asteroid)continuewhile stack and stack[-1] > 0 and stack[-1] <= abs(asteroid):if stack[-1] == abs(asteroid):asteroid = 0stack.pop(-1)if (len(stack) == 0 or stack[-1] < 0) and asteroid != 0:stack.append(asteroid)return stack   

• Version 2

class Solution:def asteroidCollision(self, asteroids: List[int]) -> List[int]:stack = []for asteroid in asteroids:while asteroid != 0:if asteroid > 0 or len(stack) == 0 or stack[-1] < 0:stack.append(asteroid)breakif stack[-1] > abs(asteroid):breakif stack[-1] == abs(asteroid):asteroid = 0stack.pop(-1)return stack

Reference

1. https://leetcode.com/problems/asteroid-collision/