Va chạm tiểu hành tinh trong C++

Mô tả bài toán

Cho mảng asteroids, giá trị tuyệt đối = kích thước, dấu = hướng (dương = phải, âm = trái). Tốc độ như nhau. Khi va chạm: nhỏ hơn nổ, bằng nhau cả hai nổ. Cùng hướng không bao giờ gặp. Trả về trạng thái sau tất cả va chạm.

Ví dụ: [5,10,-5] → [5,10] (10 và -5 va chạm, 10 thắng; 5 và 10 cùng hướng).

Giải thuật Stack

1. Duyệt mảng, dùng stack lưu tiểu hành tinh còn sống.
2. Với ast hiện tại:
   • Nếu stack rỗng hoặc đỉnh stack và ast cùng dấu (hoặc đỉnh stack âm, ast dương) → push.
   • Ngược lại (đỉnh stack dương, ast âm → va chạm):
     • So sánh kích thước: lớn hơn thắng, bằng nhau cả hai nổ.
     • Lặp lại cho đến khi không còn va chạm.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

void print_vec(vector<int> v) {
    cout << "[";
    for (int x : v) cout << x << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        vector<int> st;
        for (int a : asteroids) {
            bool alive = true;
            while (alive && !st.empty() && st.back() > 0 && a < 0) {
                if (st.back() < -a) { st.pop_back(); continue; }
                else if (st.back() == -a) { st.pop_back(); alive = false; }
                else { alive = false; }
            }
            if (alive) st.push_back(a);
        }
        return st;
    }
};

int main() {
    vector<int> v = {5, 10, -4};
    Solution ob;
    print_vec(ob.asteroidCollision(v)); // [5, 10]
    return 0;
}

Độ phức tạp

• Thời gian: O(n) (mỗi phần tử push/pop tối đa 1 lần).
• Không gian: O(n) cho stack.