768 Max Chunks To Make Sorted II

768. Max Chunks To Make Sorted II

1. Question

This question is the same as "Max Chunks to Make Sorted" except the integers of the given array are not necessarily distinct, the input array could be up to length2000, and the elements could be up to10**8.

Given an arrayarrof integers (not necessarily distinct), we split the array into some number of "chunks" (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

Example 1:

Input: arr = [5,4,3,2,1]

Output: 1

Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted.

Example 2:

Input: arr = [2,1,3,4,4]

Output: 4

Explanation:
We can split into two chunks, such as [2, 1], [3, 4, 4].
However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.

Note:

• arrwill have length in range[1, 2000].

• arr[i]will be an integer in range[0, 10**8].

2. Implementation

(1) DP

思路: 这题和769最大的不同是，数组里的数会出现重复，而且数字的范围也不是严格在[0, arr.length - 1]的范围中，所以无法像上一题一样利用当前最大值和index的关系找到最多的chunk。但通过观察我们可以发现，当在[0, i]位置上的当前最大数是小于[i + 1, n -1]上的最小数时，我们知道可以形成一个chunk，所以我们建立两个数组leftMax, rightMin分别存储在位置i上从左到右的最大数，和从右到左的最小数，最后再通过比较这两个数组上的值得到结果，注意结果最后是res + 1，因为一个极端的情况是数组是[5, 4, 3, 2, 1]这样单调递减的, 其实res的值为0

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int n = arr.length;

        int[] leftMax = new int[n];
        int[] rightMin = new int[n];

        int curMax = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            curMax = Math.max(curMax, arr[i]);
            leftMax[i] = curMax;
        }

        int curMin = Integer.MAX_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            curMin = Math.min(curMin, arr[i]);
            rightMin[i] = curMin;
        }

        int res = 0;
        for (int i = 0; i < n - 1; i++) {
            if (leftMax[i] <= rightMin[i + 1]) {
                ++res;
            }
        }
        return res + 1;
    }
}

3. Time & Space Complexity

DP: 时间复杂度O(n), 空间复杂度O(n)