735. Asteroid Collision
Tags:
Medium
Skills:
Stack
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu mô phỏng các vụ va chạm giữa các thiên thạch trong một hàng, dựa trên kích thước và hướng di chuyển của chúng. Các thiên thạch di chuyển sang phải (giá trị dương) và sang trái (giá trị âm). Khi hai thiên thạch gặp nhau, kết quả phụ thuộc vào kích thước của chúng:
Approach
Sử dụng stack để mô phỏng các vụ va chạm → Xử lý các vụ va chạm theo thứ tự ngược lại
Solution
1function asteroidCollision(asteroids: number[]): number[] {
2 const stack: number[] = [];
3
4 for (const a of asteroids) {
5 let destroy = false;
6
7 while (stack.length > 0 && a < 0 && stack.at(-1) > 0) {
8 const top = stack.at(-1);
9
10 if (top < Math.abs(a)) {
11 stack.pop()
12 } else if (top === Math.abs(a)) {
13 stack.pop()
14 destroy = true;
15 break;
16 } else {
17 destroy = true;
18 break;
19 }
20 }
21
22 if (!destroy) {
23 stack.push(a);
24 }
25 }
26
27 return stack
28}