Leetcode 735 - Asteroid Collision

題目

Problem#

給你一個整數陣列 asteroids 其中的數字正負代表方向(正=右，負=左)，數值的絕對值代表大小
每個小行星沿著各自的方向運動，速度相同。方向相對的發生碰撞；方向相反則永遠不會發生碰撞。發生相撞時大的留下來，小的則消失，如果大小相同則兩個都消失。
問你撞到最後，留下來的有哪些？

測資限制#

• $2 \le n \le 10^4$
• $-1000 \le val \le 1000, val \neq 0$

想法#

用 stack 從左往右掃，當數字 $i > 0$ 且當前 stack 頂端的數字 $< 0$ 時（代表相撞），則判斷大小並推回 stack 中，如果沒有則直接進 stack
掃完一次後可能還沒撞完所有的小行星，當當前陣列裡頭沒有任何 $i > 0, j < 0$ 時則結束

• 時間複雜度: $\mathcal{O}(nk)$
  • $k$: 相撞次數
• 空間複雜度: $\mathcal{O}()$

AC Code#

Copy

class Solution {
public:
    bool check(vector<int>& v)
    {
        int n = v.size();
        for(int i = 0; i < n-1; i++)
            if(v[i] > 0 && v[i+1] < 0)
                return 1;
        return 0;
    }
    vector<int> solve(vector<int>& v)
    {
        int n = v.size();
        stack<int> s;
        for(int i = 0; i < n; i++)
        {
            int b = v[i];
            if(!s.empty())
            {
                int a = s.top();
                if(a > 0 && b < 0)
                {
                    s.pop();
                    if(a > abs(b))
                        s.push(a);
                    else if(a < abs(b))
                        s.push(b);
                }
                else
                    s.push(b);
            }
            else
                s.push(b);
        }
 
        vector<int> ans;
        while(!s.empty())
            ans.push_back(s.top()), s.pop();
        reverse(ans.begin(), ans.end());
        return ans;
    }
 
    vector<int> asteroidCollision(vector<int>& ast) {
        vector<int> ans;
         ans = solve(ast);
 
         while(check(ans))
             ans = solve(ans);
 
        return ans;
    }
};

view raw leetcode/735.cpp delivered with ❤ by emgithub

賞析#

官方題解有 $O(n)$ 的做法