justExercise/AsteroidCollision735.cpp at master · studentBC/justExercise · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        vector<int>ans;
        for (int ast:asteroids) {
            if (!ans.empty()) {
                while (1) {
                    if (ans.size() > 0 && ans.back() > 0 && ast < 0) {
                        if (ans.back() > -ast) {
                            ast = 0;
                        } else if (ans.back() < -ast) {
                            ans.pop_back();
                        } else {
                            ans.pop_back();
                            ast = 0;
                            break;
                        }
                    } else {
                        if (ast != 0) {
                            ans.push_back(ast);
                        }
                        break;
                    }
                }
            } else {
                ans.emplace_back(ast);
            }
        }
        return ans;
    }
};
//8 ms solution
class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
      int n = asteroids.size();
      stack<int> stk;

      for (int i = 0; i < n; i++) {
        int a = asteroids[i];
        if (a > 0) stk.push(a);
        else {
          bool exploded = false;
          while (!stk.empty()) {
            if (stk.top() < 0) break;
            if (stk.top() + a >= 0) {
              exploded = true;
              if (stk.top() + a == 0) stk.pop();
              break;
            } else stk.pop();
          }
          if (!exploded) stk.push(a);
        }
      }
      vector<int> ret(stk.size(), 0);
      int idx = ret.size() - 1;
      while (!stk.empty()) {
        ret[idx--] = stk.top();
        stk.pop();
      }
      return ret;
    }
};