2289. Steps to Make Array Non-decreasing

#stack

題目

LeetCode Problem

You are given a 0-indexed integer array nums. In one step, remove all elements nums[i] where nums[i - 1] > nums[i] for all 0 < i < nums.length.

Return the number of steps performed until nums becomes a non-decreasing array.

說明

這題我在看完 Hint 後才想出來，所以紀錄一下。

  1. 一個元素被移除 if and only if 左邊有比他大的數
  2. 一個元素被移除的時候一定是左邊第一個比他大的數和他之間沒有其他數字
  3. 所以該元素被移除的回數會是 max(左邊第一個比他大的數和他之間的數字回數) + 1
  4. 也就是說原本問題被轉換成「max(每個數字被移除的回數)」
  5. 「左邊第一個比他大的數字」可以用單調（遞增） stack 維護，如此，對陣列由左至右的走訪可以 O(N) 解決整個問題。

Code

 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

class Solution {
public:
    int totalSteps(vector<int>& nums) {
        int ans = 0;
        stack<pair<int, int>> stk;        
        for (auto v: nums) {
            int maxDist = 0;
            while (!stk.empty()) {
                auto [val, dist] = stk.top();
                if (val > v) {
                    break;
                }
                stk.pop();
                maxDist = max(maxDist, dist);
            }
            
            int dist = 0;
            if (!stk.empty()) {
                dist = maxDist + 1;
                ans = max(ans, dist);
            }
            
            stk.emplace(v, dist);
            
        }
        return ans;
    }
};