LeetCode 735 Asteroid Collision

LeetCode

We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

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.

Constraints:

2 <= asteroids.length <= 10<sup>4</sup> -1000 <= asteroids[i] <= 1000
* asteroids[i] != 0

题目大意：

星体向左向右同速运动，符号表示方向，数值表示星体大小。若相撞，同大小想消，否则较小的消失。

解题思路：

保持原有顺序且相邻元素大小关系，考虑用Stack

解题步骤：

N/A

注意事项：

1. 两星体可以正负，所以有四种可能：同左，同右，向左向右，向右向左。只有最后一种向右向左才会相撞。所以出栈条件为栈顶为正，遍历元素为负。
2. 同大小要特别处理，记录到is_same_size变量中。入栈条件为出栈条件的非以及不是is_same_size

Python代码：

def asteroidCollision(self, asteroids: List[int]) -> List[int]:
	stack = []
	for i in range(len(asteroids)):
		is_same_size = False
		while stack and stack[-1] > 0 and asteroids[i] < 0 and -asteroids[i] >= stack[-1]:
			stack_top = stack.pop()
			if stack_top == -asteroids[i]:
				is_same_size = True
				break
		if not (stack and stack[-1] > 0 and asteroids[i] < 0) and not is_same_size:
			stack.append(asteroids[i])
	return stack

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

更简洁的写法，不要要掌握while, break, else语句，如果没有break，else永远执行，若break，else不执行。若不熟悉该语法，推荐用上法。

Python代码：

def asteroidCollision2(self, asteroids: List[int]) -> List[int]:
	stack = []
	for i in range(len(asteroids)):
		while stack and stack[-1] > 0 and asteroids[i] < 0:
			if -asteroids[i] < stack[-1] or stack.pop() == -asteroids[i]:
				break
		else:
			stack.append(asteroids[i])
	return stack