algo-aha

数组分段排序后连接、总体也有序，最多可分多少段

• https://leetcode.com/problems/max-chunks-to-make-sorted-ii/

数组数任意可重复

int maxChunksToSorted(vector<int>& arr) {
    // maxL[i]表示arr[0..i)的最大值，minR[i]表示arr[i..]的最小值
    // maxL[i]<=minR[i]时可分
    const int N = arr.size();
    vector<int> maxL(N + 1, INT_MIN), minR(N + 1, INT_MAX);
    for (int i = 0; i < N; i++) {
        maxL[i+1] = max(maxL[i], arr[i]);
    }

    int ans = 0;
    for (int i = N - 1; i >= 0; i--) {
        minR[i] = min(minR[i+1], arr[i]);
        if (maxL[i] <= minR[i]) ans++;
    }
    return ans;
}

• https://leetcode.com/problems/max-chunks-to-make-sorted/

上题解法可用。因为数组是[1,n]的排列，还可以简化

int maxChunksToSorted(vector<int>& arr) {
    // 数组是[1,n]的排列，若maxL[i]==i，则在i后可断开左右
    int ans = 0;
    int maxL = INT_MIN;
    for (int i = 0; i < arr.size(); i++) {
        maxL = max(maxL, arr[i]);
        if (maxL == i) ans++;
    }
    return ans;
}

最短无序子段，该子段排序后、整个数组也有序

• https://leetcode.com/problems/shortest-unsorted-continuous-subarray/

int findUnsortedSubarray(vector<int>& nums) {
    // 若数组有序，对任意nums[i]有：maxL[i]==nums[i]==minR[i]
    // 从左往右检查，最右的违反maxL[i]==nums[i]的i是右边界
    // 从右往左检查，最左的违反nums[i]==minR[i]的i是左边界
    const int N = nums.size();
    int maxL = INT_MIN, minR = INT_MAX;
    int lo = 0, hi = -1; // 无序子段的左右边界
    for (int i = 0, j = N - 1; i < N; i++, j--) {
        maxL = max(maxL, nums[i]);
        if (nums[i] != maxL) hi = i;
        
        minR = min(minR, nums[j]);
        if (nums[j] != minR) lo = j;
    }
    return hi - lo + 1;
}