大魚吃小魚

本題同 2289. 使數組按照非遞減順序排序

思路

給定一個陣列，比如 $[4,3,2,3,2,1]$ ，每個數字代表魚的大小，
每一輪次，比較大隻的魚都會往右吃掉最近的，比自己小的魚。
上面的陣列變化是這樣的： $[4,3,2,3,2,1]\to[4,3]\to[4]$ 。

• 第一輪：從右往左看，1 被 2 吃掉，2 被 3 吃掉, 2 被 3 吃掉, 3 被 4 吃掉。
• 第二輪：3 被 4 吃掉。

假如陣列是 $[8,9,2,4]$ ，經過一輪時，8, 9 共同吃掉 2，而不是吃掉 2, 4 兩條魚。

對於此題目，我們為每條魚記錄一個「輪次」的資訊，方便被吃掉的魚將資訊往被吃掉的魚傳遞。
舉個例子： $[8,3,1,5,6,7,2,4]$ ，倒序遍歷，棧中元素單調遞減。

• 8 進入
  • 花費 1 回合吃掉 3，3 需要花 1 回合做好它要做的事情，兩者取 $\max(1,1)=1$ 。
  • 再花費 1 回合吃掉 5, 5 需要花 0 回合做好它要做的事情，兩者取 $\max(2,0)=2$
  • 再花費 1 回合吃 6, 6 需要花 0 回合做好它要做的事情，兩者取 $\max(3,0)=3$
  • 再花費 1 回合吃 7，7 需要花 2 回合做好它要做的事情，兩者取 $\max(4,2)=4$

程式碼

單調棧

class Solution {
private:
    static const int MX = 1e5+1;
    int stk[MX][2]; // 紀錄數字, 以及所需的輪次
public:
    int totalSteps(vector<int>& nums) {
        int n = nums.size();
        int res = 0;
        int j = -1; // 指向棧頂的位置
        for(int i = n - 1; i >= 0; i--) { 
            int curTurn = 0; // 當前的數字需要花多少回合刪掉後面的數字
            while(j >= 0 && stk[j][0] < nums[i]) {
                curTurn = max(curTurn + 1, stk[j][1]);
                --j;
            }
            ++j;
            stk[j][0] = nums[i];
            stk[j][1] = curTurn;
            res = max(res, curTurn);
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$