# 768. Max Chunks To Make Sorted II 最多能完成排序的块 II

## # 题目描述：

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:

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

## # 解题方法

Grandyang大神的可排序的最大块数之二open in new window一文已经总结的非常好了，先给他赞一个。

### # 方法一：

`````` 2  1    4  3    4

(1  2)  (3  4)  (4)

1  2    3  4    4
``````

`````` 2  1     5   2   4

(1  2)   (2   4   5)

1  2     2   4   5
``````

``````class Solution(object):
def maxChunksToSorted(self, arr):
"""
:type arr: List[int]
:rtype: int
"""
asort = sorted(arr)
res = 0
sum1 = 0
sum2 = 0
for i, a in enumerate(arr):
sum1 += a
sum2 += asort[i]
if sum1 == sum2:
res += 1
sum1 = 0
sum2 = 0
return res
``````

### # 方法二：

``````nums    2   1   3   4   4
f       2   2   3   4   4
b       1   1   3   4   4

``````

``````class Solution(object):
def maxChunksToSorted(self, arr):
"""
:type arr: List[int]
:rtype: int
"""
n = len(arr)
res = 1
f, b = [0] * n, [0] * n
f[0] = arr[0]
b[-1] = arr[-1]
for i in range(1, n):
f[i] = max(arr[i], f[i - 1])
for i in range(n - 2, -1, -1):
b[i] = min(arr[i], b[i + 1])
for i in range(n - 1):
if f[i] <= b[i + 1]:
res += 1
return res
``````

### # 方法三：

stack：1

stack：1

stack：1，3

stack：1，3，3

stack：1，3

``````class Solution(object):
def maxChunksToSorted(self, arr):
"""
:type arr: List[int]
:rtype: int
"""
n = len(arr)
stack = list()
stack.append(arr[0])
curMax = arr[0]
for i in range(1, n):
if arr[i] >= stack[-1]:
stack.append(arr[i])
else:
curMax = stack[-1]
while stack and arr[i] < stack[-1]:
stack.pop()
stack.append(curMax)
return len(stack)
``````

http://www.cnblogs.com/grandyang/p/8850299.html

## # 日期

2018 年 10 月 3 日 —— 玩游戏导致没睡好，脑子是浆糊。