# 【基础篇 - Day 6】 2020-11-06 - 768. 最多能完成排序的块 II（01. 数组，栈，队列 ）
# 题目描述
# 入选理由
1.和讲义的相关专题关联度很大， 检验大家相关专题的掌握程度。为了不剧透，我就不说是哪个专题了。 2.题目难度是 hard，适合放在最后一天压轴。 \3. 可以简单实现，也可以优化。 因此适合写出暴力解再优化。
# 题目描述
这个问题和“最多能完成排序的块”相似，但给定数组中的元素可以重复，输入数组最大长度为 2000，其中的元素最大为 108。
arr 是一个可能包含重复元素的整数数组，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。
我们最多能将数组分成多少块？
示例 1:
输入: arr = [5,4,3,2,1] 输出: 1 解释: 将数组分成 2 块或者更多块，都无法得到所需的结果。 例如，分成 [5, 4], [3, 2, 1] 的结果是 [4, 5, 1, 2, 3]，这不是有序的数组。 示例 2:
输入: arr = [2,1,3,4,4] 输出: 4 解释: 我们可以把它分成两块，例如 [2, 1], [3, 4, 4]。 然而，分成 [2, 1], [3], [4], [4] 可以得到最多的块数。 注意:
arr 的长度在[1, 2000]之间。 arr[i]的大小在[0, 108]之间。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/max-chunks-to-make-sorted-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
# 我的回答
# 解法一
# 时空复杂度
时间复杂度：O(n)
空间复杂度: O(n)
单调栈解法：因为要找到做多的快，所以每一个递减区域都可以分成一个块，那么就可以转化成问题：找到第一个比他大的值，也就是单调栈解法。
当每次找到第一个最大值，将前面的块只需要保存一个极值，这样只需要返回栈的长度即可
var maxChunksToSorted = function (arr) {
const stack = [];
for (let i = 0; i < arr.length; i++) {
let curr = arr[i];
if (stack.length > 0 && stack[stack.length - 1] > curr) {
const peek = stack.pop()
while (stack && stack[stack.length - 1] > curr) stack.pop();
stack.push(peek);
} else {
stack.push(curr);
}
}
return stack.length;
};
# 解法二
时间复杂度：O(nlogn) 排序的复杂度
空间复杂度: O(n)
滑动窗口解法：根据题意中 每个可排序块的总和应该是恒等的 所以将和相加，每一个和相等的实际就是一次切分块的点
var maxChunksToSorted = function (arr) {
const newArr = [...arr]
const sortArr = newArr.sort((a, b) => a - b)
let count = 0, sum1 = 0, sum2 = 0
for (let i = 0; i < arr.length; i++) {
sum1 += arr[i]
sum2 += sortArr[i]
if (sum1 == sum2) {
count++
}
}
return count
};