769_MaxChunksToMakeSorted - a920604a/leetcode GitHub Wiki

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        stack<pair<int,int>> sta;
        int n =arr.size();
        for(int i=0;i<n;++i){
            int mn = arr[i], mx = arr[i];
            while(!sta.empty()){
                auto top = sta.top();
                if(arr[i] < top.second){
                    mn = min(top.first, mn);
                    mx = max(top.second, mx);
                    sta.pop();
                }
                else break;
            }
            sta.push({mn, mx});
        }
        return sta.size();
    }
};

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int ret = 0, n = arr.size();
        for(int i=0;i<n;++i){
            int cur = arr[i], j= i+1;
            for(;j<=cur;++j){
                cur = max(cur, arr[j]);
                if(cur >= arr.back()) return ret+1;
            }
            i = j-1;
            ++ret;
            
        }
        return ret;
    }
};

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int mx = 0, ret =0, n= arr.size();
        for(int i=0;i<n;++i){
            mx = max(arr[i], mx);
            if(mx == i) ret++;
        }
        return ret;
    }
};