🔗 🔴 2751. Robot Collisions 2092

tags: Weekly Contest 351 陣列(Array) 堆疊(Stack) 排序(Sorting) 模擬(Simulation)

題意

有 nn 個機器人，編號從 11 到 nn，每個機器人都有其在一條直線上的位置、生命值和移動方向。

給定兩個下標從 00 開始的整數陣列 positions\text{positions}、healths\text{healths} 和一個字串 directions\text{directions} ，分別代表每個機器人的位置、生命值和移動方向。其中 directions[i]\text{directions}[i] 只會是 ′L′'L' 表示向左或 ′R′'R' 表示向右，且 positions\text{positions} 中的所有整數都是唯一的。

所有機器人會同時以相同的速度按照給定的方向在直線上移動。如果兩個機器人移動到相同位置，他們會發生碰撞。

  • 如果兩個機器人發生碰撞，生命值 較低 的機器人會被 移除 ，而另一個機器人的生命值會 減少一點。存活的機器人會繼續朝原本的方向移動。如果兩個機器人的生命值 相同 ，他們 都會被移除 。

你的任務是確定在所有碰撞結束後，存活機器人的生命值，並按照機器人原本的順序輸出，即機器人 11 的最終生命值（如果存活）、機器人 22 的最終生命值（如果存活），依此類推。如果沒有存活的機器人，就回傳一個空陣列。

請回傳一個陣列，包含在不再發生碰撞後剩餘機器人的生命值（按照輸入時的編號順序）。

注意：positions\text{positions} 可能是無序的。

思路：排序(Sorting) + 堆疊(Stack) + 模擬(Simulation)

首先根據機器人的位置對機器人進行 排序(Sorting) ，這樣可以確保我們按照位置順序處理碰撞，而不是按照輸入的順序。

之後使用 堆疊(Stack) stst 維護向右移動的機器人，另外由於最後要返回剩餘機器人的生命值，我們還需要使用一個列表 leftleft 來維護向左移動且已經不會再發生碰撞的機器人。

接著按照位置的順序（由左至右）遍歷機器人，對於每個機器人，根據其移動方向進行不同的處理：

  • 如果機器人向右移動，則可以直接將其加入堆疊 stst 中。
  • 如果機器人向左移動，則堆疊 stst 中的機器人會與其發生碰撞，我們需要對其進行碰撞處理：
    • 當堆疊 stst 不為空且堆疊頂部機器人的生命值小於當前機器人時，移除堆疊頂部的機器人，並將當前機器人的生命值減少。
    • 如果堆疊頂部機器人的生命值等於當前機器人，則兩個機器人都被移除。
    • 如果堆疊頂部機器人的生命值大於當前機器人，則當前機器人被移除，堆疊頂部機器人的生命值減少。
  • 如果堆疊 stst 為空，則當前機器人會往左移動，且不會再發生碰撞，將其加入列表 leftleft 中。

最後，將未被移除的向右移動的機器人從堆疊 stst 中加入列表 leftleft 中，並根據機器人的原始編號對列表 leftleft 進行排序，返回其生命值。

複雜度分析

  • 時間複雜度：O(nlog⁡n)\mathcal{O}(n \log n)，排序需要 O(nlog⁡n)\mathcal{O}(n \log n)，處理每個機器人的碰撞需要 O(n)\mathcal{O}(n)，總時間複雜度為 O(nlog⁡n)\mathcal{O}(n \log n)。
  • 空間複雜度：O(n)\mathcal{O}(n)，使用了額外的堆疊和列表來存儲機器人的信息。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:
        n = len(positions)
        robots = sorted(zip(range(n), positions, healths, directions), key = lambda x: x[1])
        
        st = [] # 保存向右移動的機器人
        left = [] # 保存向左移動，且已經不會再發生碰撞的機器人
        for i, _, h, d in robots:
            if d == 'R': # 向右的機器人
                st.append([i, h])
            else: # 向左的機器人
                while st and st[-1][1] < h: # 把前面向右的機器人碰撞掉
                    h -= 1
                    st.pop()
                if st: # 還有向右的機器人，當前的會被碰撞掉
                    if st[-1][1] == h:
                        st.pop()
                    else: # st[-1][1] > h
                        st[-1][1] -= 1
                else:
                    left.append([i, h])
        left += st
        left.sort(key = lambda x: x[0])
        return [h for _, h in left]
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
class Solution {
public:
    vector<int> survivedRobotsHealths(vector<int>& positions, vector<int>& healths, string directions) {
        int n = positions.size();
        vector<int> id(n);
        iota(id.begin(), id.end(), 0);
        sort(id.begin(), id.end(), [&](int i, int j) {
            return positions[i] < positions[j]; // sort by position
        });

        stack<int> st;
        vector<int> left;
        for (int i: id) {
            if (directions[i] == 'R') {
                st.push(i);
            }
            else {
                while (!st.empty() && healths[st.top()] < healths[i]) {
                    healths[i]--;
                    st.pop();
                }
                if (!st.empty()) {
                    if (healths[st.top()] == healths[i]) st.pop();
                    else healths[st.top()]--;
                }
                else {
                    left.push_back(i);
                }
            }
        }

        while (!st.empty()) {
            left.push_back(st.top());
            st.pop();
        }
        sort(left.begin(), left.end());
        vector<int> ans;
        for (int i: left) ans.push_back(healths[i]);
        return ans;
    }
};

類題

寫在最後

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail,
1 girl, solo, long hair, black hair, blue eyes, skirt, shirt, school uniform, standing, white shirt, short sleeves, pleated skirt, outdoors, sky, serafuku, (pink serafuku, pink school uniform), day, sailor collar, blurry, arm up, neckerchief, long skirt, girl