问题
给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。
我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。
返回数组能分成的最多块数量。
示例 1:
输入: arr = [4,3,2,1,0] 输出: 1 解释: 将数组分成2块或者更多块，都无法得到所需的结果。 例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。
示例 2:
输入: arr = [1,0,2,3,4] 输出: 4
解释:
我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。 然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。 提示:
- n == arr.length
- 1 <= n <= 10
- 0 <= arr[i] < n
- arr 中每个元素都 不同
AC思路
迭代整个列表，因为 arr ，它表示在 [0, n - 1] 范围内的整数的排列。元素小于之前最大的元素就不得不融为一体，成为一个块。（因为比当前元素大，在排序后一定会出现在改元素后面），当第 i 个元素大于 前 i - 1 个元素中最大的元素的时候，说明其本身在前 i 个元素中是最靠后的，能独立称为一个块。
[1,0,2,3,4] [4,3,2,1,0] [0,1,2,3,4] [0,1,2,3,4]
代码
var maxChunksToSorted = function(arr) { let count = 0 let max = 0 for(let i = 0; i < arr.length; i++){ max = Math.max(max,arr[i]) if(max === i) count ++ } return count };
最多能完成排序的块 II
问题
AC思路
[1,2,3,4,5] 可以分为 5 个块，而[2,1,3,4,5]最多分为 4 个块，观察题意我们可以发现只要当前元素小于之前元素的最大值，就不得不和它们玩在一起。（拼成一个块）
例如[4,2,1,5]遍历到元素 2 的时候，就只能和 4 这个家伙混在一起，当遍历到 1 当时候，就只能和 4 2这两个家伙玩在一起拼成一个块，而遍历到 5 的时候 ，5是目前为止最大的，所以它可以一个人玩（一个独立的块）。
但是[3,6,7,4]这种情况就是 6 7 得和 4 拼成一个快，但是和上题不同的是，本题内元素可以重复，所以排序后的结果无法用下标来对应。但是单调栈可以很好的帮助我们解决问题
- 那为什么要使用单调栈呢 ？ 原因也很简单，迭代元素的时候发现大于之前最大的，就能独立成为一个块，使用
单调递增栈能帮助我们维护所有的块以及每个块最大的元素。 比如[1,0]实际上我们只需要记录 1 即可，后面只需要比 1 大那么它就是一个独立的块，如果这块不太清楚还是直接看代码好理解一点。
AC代码
var maxChunksToSorted = function(arr) { const stack = [] // 递增栈 for(let i = 0; i < arr.length; i++){ // 第一个元素进来没人比较自己成为一个块，后面的元素比栈顶大就是独立的元素 if(stack.length === 0 || arr[i] >= stack[stack.length - 1]){ stack.push(arr[i]) }else{ // [1,2,0] 当迭代到 0 的时候，不断弹出栈中的元素，保证 0 能融入其中。记录这个块中的最大值。 let max = stack.pop() while(stack.length && stack[stack.length - 1] > arr[i]){ stack.pop() } stack.push(max) } } return stack.length };
