LeetCode/最多能完成排序的块

1. 最多能完成排序的块I

给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。
我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。
返回数组能分成的最多块数量。

//从左往右遍历、融合不在位的元素
class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int ans = arr.size(), max_ = 0;
        for (int i = 0; i < arr.size(); ++i) {
            max_ = max(max_, arr[i]);
            if (max_ != i) ans--;//不在位则融合
        }
        return ans;
    }
};

2. 最多能完成排序的块II

arr是一个可能包含重复元素的整数数组,元素为任意整数

2.1 单调栈

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        stack<int> s;//单调栈，记录当前块最大元素，用于分组融合
        for (auto &num : arr) {
            if (s.empty() || num >= s.top()) //注意处理空栈
                s.push(num);//大于之前分组，则新增块
            else {//否则进行融合
                int mx = s.top();//融合前记录分组最大元素
                s.pop();
                while (!s.empty() && s.top() > num) //单调栈融合
                    s.pop();
                s.push(mx);//放回分组最大元素
            }
        }
        return s.size();//返回分组个数
    }
};

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        stack<int> s;
        s.push(INT_MIN);//作为栈底
        for(int x: arr){
            int y = max(x, s.top());
            while(s.top() > x) s.pop();
            s.push(y);
        }
        return s.size() - 1;
    }
};

2.2 哈希表

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        unordered_map<int, int> cnt;//哈希表计数判断分块
        int res = 0;
        vector<int> sortedArr = arr;//新增排序辅助数组
        sort(sortedArr.begin(), sortedArr.end());
        for (int i = 0; i < sortedArr.size(); i++) {//从左往右遍历
            int x = arr[i], y = sortedArr[i];
            cnt[x]++;//对x正向计数
            if (cnt[x] == 0) 
                cnt.erase(x);
            cnt[y]--;//对y反向计数
            if (cnt[y] == 0) 
                cnt.erase(y);

            if (cnt.size() == 0)//计数消除说明前面排序后相同，新增一组
                res++;
        }
        return res;
    }
};

2.3 前缀和(未证明)

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int n = arr.size();
        auto sortArr = arr;
        sort(sortArr.begin(), sortArr.end());

        int ans = 0;
        // 前缀和相同，则表示可独立出一个块
        long long sum = 0, sortSum = 0;
        for (int i = 0; i < n; i++) {
            sum += arr[i];//计算未排序前缀和
            sortSum += sortArr[i];//计算排序前缀和

            ans += (sum == sortSum);//相等说明前面元素排序后相同,分组加一
        }

        return ans;
    }
};

2.4 记录右侧最小值和左侧最大值（接雨水）

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        vector<int> rightmin(arr.size());
        int rmin = INT_MAX;
        for(int i=arr.size()-1;i>=0;i--){//记录右侧最小元素
            rightmin[i] = rmin;
            rmin = min(rmin,arr[i]);
        }
        int lmax = INT_MIN;
        int res = 0;
        for(int i=0;i<arr.size();i++){
            lmax = max(lmax,arr[i]);//记录当前最大值
            if(lmax<=rightmin[i]) res++;//左侧最大值小于右侧最小值，说明满足分组
        }
        return res;
}
};