3542. 將所有元素變為 0 的最少操作次數

思路

每次操作，能選擇一個子數組，找到最小值，把所有的最小值設為零。
找出把整個數組歸零的最小操作次數。

假如想要將數組[1,0,1]歸零，一定要兩次操作，因為要想把1經過操作歸零，選定的子數組不能包含更小的數字0。

也就是說，假如一個數字x，它的左右側都有比自己小的數字，
要想讓x歸零，就不能選定包含左右兩邊的區塊，自己必須要額外花一個操作把x歸零。

所以，用一個單調棧（嚴格遞增）紀錄現在存放的數字，當遇到的數字要比棧頂小時，
位於棧頂的數字，就需要花費操作一次。

最後，留在棧裡面的數字也需要操作，因此最後加上棧的大小，
另外，如果棧有放入數字 0，相當於多算了一次，要扣回去（因為棧是單調遞增，只要檢查第一個數字）。

程式碼

1. 單調棧

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int res = 0;
        vector<int> stk;
        for(int x : nums) {
            // 如果棧頂的數字比較大，那麼它一定得做一次操作將自己變為 0 
            while(!stk.empty() && stk.back() > x) {
                ++res;
                stk.pop_back();
            }
            // 同樣的數字只需要刪除一次 
            if(stk.empty() || stk.back() < x) {
                stk.push_back(x);
            }
        }
        return res + stk.size() - (stk[0] == 0);
    }
};

2. 單調棧，省空間版本

class Solution {
    public:
    int minOperations(vector<int>& nums) {
        int n = nums.size();
        int res = 0;
        int j = -1;
        for(int i = 0; i < n; ++i) {
            
            while(j >= 0 && nums[j] > nums[i]) {
                ++res;
                --j;
            }            
            // stk 的大小是 j + 1, 
            // 如果最後留下來的數字如果不是 0，需要操作一次，相當於那個 + 1 有用
            // 如果是 0，那個 + 1 剛好去掉。
            if(j < 0 || nums[j] != nums[i]) { 
                nums[++j] = nums[i];
            }
        }

        return res + j + (nums[0] > 0);
    }
};

複雜度分析

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