3542. Minimum Operations to Convert All Elements to Zero

You are given an array nums of size n, consisting of non-negative integers. Your task is to apply some (possibly zero) operations on the array so that all elements become 0.

In one operation, you can select a subarray [i, j] (where 0 <= i <= j < n) and set all occurrences of the minimum non-negative integer in that subarray to 0.

Return the minimum number of operations required to make all elements in the array 0.

A subarray is a contiguous sequence of elements within an array.

Monotonic Stack

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int res = 0;
        vector<int> st{0};
        for(auto& n : nums) {
            while(st.back() > n) st.pop_back();
            if(st.back() < n) {
                res++;
                st.push_back(n);
            }
        }
        return res;
    }
};

Merge Interval

class Solution {
public:
    int minOperations(vector<int>& nums) {
        map<int,vector<int>> at;
        int n = nums.size(), res = 0;
        vector<int> le(n), ri(n);
        for(int i = 0; i < n; i++) {
            le[i] = ri[i] = i;
            if(nums[i]) at[-nums[i]].push_back(i);
        }
        auto merge = [&](int i, int j) {
            ri[i] = ri[j];
            le[j] = le[i];
        };
        for(auto& [_, vec] : at) {
            while(vec.size()) {
                auto p = vec.back(); vec.pop_back();
                if(ri[p] != p) continue;
                if(p + 1 < n and nums[p+1] >= nums[p]) merge(p,p+1);
                while(le[p] and nums[le[p]-1] >= nums[p]) merge(le[p]-1,p);
                res++;
            }
        }
        return res;
    }
};

Binary Search + Segment tree + Divide and Conquer

struct Seg{
    int mi,ma,val;
    Seg *left, *right;
    Seg(vector<int>& A, int l, int r): mi(l), ma(r), val(INT_MAX), left(nullptr), right(nullptr) {
        if(l^r) {
            int m = l + (r - l) / 2;
            left = new Seg(A,l,m);
            right = new Seg(A,m+1,r);
            val = min(left->val, right->val);   
        } else val = A[l];
    }
    int query(int l, int r) {
        if(l <= mi and ma <= r) return val;
        if(l > ma or r < mi) return INT_MAX;
        return min(left->query(l,r), right->query(l,r));
    }
};
class Solution {
    Seg* seg;
    int res;
    unordered_map<int,vector<int>> at;
    void helper(int l, int r) {
        if(l > r) return;
        int mi = seg->query(l,r);
        if(mi) res++;
        vector<int>& S = at[mi];
        auto it = lower_bound(begin(S), end(S), l);
        while(l <= r) {
            if(*it != l) helper(l, min(r, *it - 1));
            l = *it + 1;
            it++;
        }
    }
public:
    int minOperations(vector<int>& nums) {
        seg = new Seg(nums,0,nums.size()-1);
        res = 0;
        at.clear();
        for(int i = 0; i < nums.size(); i++) at[nums[i]].push_back(i);
        for(auto& [_, vec] : at) vec.push_back(INT_MAX - 1);
        helper(0,nums.size() - 1);
        return res;
    }
};