leet code 735. 行星碰撞

735.行星碰撞

题目解析

一道典型的运用单调栈解决的问题，元素入栈，然后当前元素和栈中元素相比较。最终得出结果。

总结反思

第一次遇到该问题的时候，脑海中没有丝毫关于单调栈的相关内容。想着双指针遍历数组解决问题。 毫无疑问能够通过一些用例，不过不是正确的解。 再次回顾，解决思路在脑海中清晰浮现

• 那么，再次遇到数组相关问题的时候。静下心来，读懂题目意思之后，要首先要思考是否能够用如下思路解决问题

1. 二分法
2. 单调栈
3. 滑动窗口
4. 双重循环

• 再然后，解决题目的时候要学会关注题目中给定的数据量级。根据数据量级判断是否能够双重或者多重循环来解决问题
• 举例：当数据量级达到 左右的时候，可以明确不能够使用双重循环来解决问题了。
• 其次：要冷静，冷静才能够发挥出脑袋最大的能力

show code

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> stack = new LinkedList<>();

        for (int asteroid : asteroids) {
            if(stack.isEmpty()) {
                stack.push(asteroid);
            } else {
                while(!stack.isEmpty()) {
                    // 取出栈顶元素.
                    int peek = stack.peek();
                    // 判断栈顶元素 和 当前元素的碰撞关系.
                    if(peek > 0 && asteroid < 0) {
                        // 表示会发生碰撞.
                        int ret = peek + asteroid;
                        if(ret > 0) {
                            // 表示 当前行星爆炸了.
                            break;
                        } else if (ret == 0) {
                            // 都爆炸了.
                            stack.pop();
                            break;
                        } else {
                            // 栈顶行星爆炸了.
                            stack.pop();
                            if(stack.isEmpty()) {
                                stack.push(asteroid);
                                break;
                            }
                        }
                    } else {
                        // 不会发生碰撞.
                        stack.push(asteroid);
                        break;
                    }
                }
            }
        }

        // 这里把栈中的元素转化成数组然后输出.
        int sz = stack.size();
        int[] ans = new int[sz];
        for (int i = sz - 1; i >= 0; i--) {
            ans[i] = stack.pop();
        }
        return ans;
    }
}