# 768 Max Chunks To Make Sorted II

## 768. [Max Chunks To Make Sorted II](https://leetcode.com/problems/max-chunks-to-make-sorted-ii/description/)

## 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 length_`2000`_, and the elements could be up to_`10**8`_._

Given an array`arr`of 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:**

* `arr`will have length in range`[1, 2000]`.
* `arr[i]`will be an integer in range`[0, 10**8]`.

## 2. Implementation

**(1) Stack**

思路: 从左到右扫一遍数组，用curMax记录当前的最大值，stack的顶部保存的是当前最大值。如果stack顶部的数大于当前的数，则将stack顶部元素出栈。最后stack元素个数则是chunk的个数。

```java
class Solution {
    public int maxChunksToSorted(int[] arr) {
        Stack<Integer> stack = new Stack();
        int curMax = Integer.MIN_VALUE;

        for (int num : arr) {
            curMax = stack.isEmpty() ? num : Math.max(stack.peek(), num);

            while (!stack.isEmpty() && stack.peek() > num) {
                stack.pop();
            }
            stack.push(curMax);
        }
        return stack.size();
    }
}
```

**(2) 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

```java
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)
