class Solution(object):
def maxChunksToSorted(self, arr):
count_a = collections.defaultdict(int)
count_b = collections.defaultdict(int)
ans = 0
for a, b in zip(arr, sorted(arr)):
count_a[a] += 1
count_b[b] += 1
if count_a == count_b: ans += 1
return ans
复杂度分析
时间复杂度：内部 count_a 和 count_b 的比较时间复杂度也是 $O(N)$，因此总的时间复杂度为 $O(N^2)$，其中 N 为数组长度。
空间复杂度：使用了两个 counter，其大小都是 N，因此空间复杂度为 $O(N)$，其中 N 为数组长度。
class Solution(object):
class Solution(object):
def maxChunksToSorted(self, arr):
count = collections.defaultdict(int)
non_zero_cnt = 0
ans = 0
for a, b in zip(arr, sorted(arr)):
if count[a] == -1: non_zero_cnt -= 1
if count[a] == 0: non_zero_cnt += 1
count[a] += 1
if count[b] == 1: non_zero_cnt -= 1
if count[b] == 0: non_zero_cnt += 1
count[b] -= 1
if non_zero_cnt == 0: ans += 1
return ans
复杂度分析
时间复杂度：瓶颈在于排序，因此时间复杂度为 $O(NlogN)$，其中 N 为数组长度。
空间复杂度：使用了一个 counter，其大小是 N，因此空间复杂度为 $O(N)$，其中 N 为数组长度。
class Solution:
def maxChunksToSorted(self, A: [int]) -> int:
stack = []
for a in A:
# 遇到一个比栈顶小的元素，而前面的块不应该有比 a 小的
# 而栈中每一个元素都是一个块，并且栈的存的是块的最大值，因此栈中比 a 小的值都需要 pop 出来
if stack and stack[-1] > a:
# 我们需要将融合后的区块的最大值重新放回栈
# 而 stack 是递增的，因此 stack[-1] 是最大的
cur = stack[-1]
# 维持栈的单调递增
while stack and stack[-1] > a: stack.pop()
stack.append(cur)
else:
stack.append(a)
# 栈存的是块信息，因此栈的大小就是块的数量
return len(stack)
CPP Code:
class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
stack<int> stack;
for(int i =0;i<arr.size();i++){
// 遇到一个比栈顶小的元素，而前面的块不应该有比 a 小的
// 而栈中每一个元素都是一个块，并且栈的存的是块的最大值，因此栈中比 a 小的值都需要 pop 出来
if(!stack.empty()&&stack.top()>arr[i]){
// 我们需要将融合后的区块的最大值重新放回栈
// 而 stack 是递增的，因此 stack[-1] 是最大的
int cur = stack.top();
// 维持栈的单调递增
while(!stack.empty()&&stack.top()>arr[i]){
sstackta.pop();
}
stack.push(cur);
}else{
stack.push(arr[i]);
}
}
// 栈存的是块信息，因此栈的大小就是块的数量
return stack.size();
}
};
JAVA Code:
class Solution {
public int maxChunksToSorted(int[] arr) {
LinkedList<Integer> stack = new LinkedList<Integer>();
for (int num : arr) {
// 遇到一个比栈顶小的元素，而前面的块不应该有比 a 小的
// 而栈中每一个元素都是一个块，并且栈的存的是块的最大值，因此栈中比 a 小的值都需要 pop 出来
if (!stack.isEmpty() && num < stack.getLast()) {
// 我们需要将融合后的区块的最大值重新放回栈
// 而 stack 是递增的，因此 stack[-1] 是最大的
int cur = stack.removeLast();
// 维持栈的单调递增
while (!stack.isEmpty() && num < stack.getLast()) {
stack.removeLast();
}
stack.addLast(cur);
} else {
stack.addLast(num);
}
}
// 栈存的是块信息，因此栈的大小就是块的数量
return stack.size();
}
}
JS Code:
var maxChunksToSorted = function (arr) {
const stack = [];
for (let i = 0; i < arr.length; i++) {
a = arr[i];
if (stack.length > 0 && stack[stack.length - 1] > a) {
const cur = stack[stack.length - 1];
while (stack && stack[stack.length - 1] > a) stack.pop();
stack.push(cur);
} else {
stack.push(a);
}
}
return stack.length;
};
Go Code:
func maxChunksToSorted(arr []int) int {
var stack []int // 单调递增栈, stack[-1] 栈顶
for _, a := range arr {
// 遇到一个比栈顶小的元素，而前面的块不应该有比 a 小的
// 而栈中每一个元素都是一个块，并且栈的存的是块的最大值，因此栈中比 a 小的值都需要 pop 出来
if len(stack) > 0 && stack[len(stack)-1] > a {
// 我们需要将融合后的区块的最大值重新放回栈
// 而 stack 是递增的，因此 stack[-1] 是最大的
cur := stack[len(stack)-1]
// 维持栈的单调递增
for len(stack) > 0 && stack[len(stack)-1] > a {
stack = stack[:len(stack)-1] // pop
}
stack = append(stack, cur) // push
} else {
stack = append(stack, a) // push
}
}
// 栈存的是块信息，因此栈的大小就是块的数量
return len(stack)
}
PHP Code:
class Solution
{
/**
* @param Integer[] $arr
* @return Integer
*/
function maxChunksToSorted($arr)
{
$stack = []; // 单调递增栈, stack[-1] 栈顶
foreach ($arr as $a) {
// 遇到一个比栈顶小的元素，而前面的块不应该有比 a 小的
// 而栈中每一个元素都是一个块，并且栈的存的是块的最大值，因此栈中比 a 小的值都需要 pop 出来
if ($stack && $stack[count($stack) - 1] > $a) {
$cur = $stack[count($stack) - 1];
// 维持栈的单调递增
while ($stack && $stack[count($stack) - 1] > $a) array_pop($stack);
array_push($stack, $cur);
} else array_push($stack, $a);
}
// 栈存的是块信息，因此栈的大小就是块的数量
return count($stack);
}
}
复杂度分析
时间复杂度：$O(N)$，其中 N 为数组长度。
空间复杂度：$O(N)$，其中 N 为数组长度。
总结
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
