【基础篇 - Day 6】 2023-02-18 - 768. 最多能完成排序的块 II （01. 数组，栈，队列 ）

[threedayAAAAA]

给你一个整数数组 arr 。

将 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] 可以得到最多的块数。  

提示：

1 <= arr.length <= 2000 0 <= arr[i] <= 108

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/max-chunks-to-make-sorted-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[threedayAAAAA]

方法一（滑动窗口）

思路

• 先将原数组进行排序，然后可以发现 以有序数组的任意起点为左边界，然后向右扩大
• 只要这个窗口内的有序数组值与未排序数组的和是一样的
• 那么这俩窗口内的元素肯定是一样的，只是顺序不一定一致而已
• 那么这个窗口就可以当作一个块
• 依次类推直到数组遍历结束

代码

function maxChunksToSorted(arr: number[]): number {
    const sortedArr = [...arr].sort((a, b) => a - b)
    let result = 0
    let slideSum = 0 
    let sortedSlideSum = 0
    arr.forEach((originData, index) => {
        const sortedData = sortedArr[index]
        slideSum += originData
        sortedSlideSum += sortedData
        if(slideSum === sortedSlideSum){  
            result++
            slideSum = 0
            sortedSlideSum = 0
        }
    })
    return result
};

时空复杂度

• 时间复杂度: O(NlogN),主要耗时在sort排序上
• 空间复杂度: O(1)

方法二（单调栈）

思路

• 假设我们当前按序有元素 ... A, B, ....
• A <= B时 A,B可以在两个不同的块中
• A > B 时，A 跟B一定在同一个块中，否则按升序排序后，这俩的顺序就是 A B与排序后的数组不一致
• 所以我们可以得到如下结论，当前元素不大于前一块中任意元素时即可成独立块
• 所以顺理成章的可以使用单调栈来解决此问题

代码

function maxChunksToSorted(arr: number[]): number {
    const stack = []
    arr.forEach(item => {
        if(stack.length && item < stack[stack.length - 1]){
            const max = stack[stack.length - 1]
            while(stack.length && item < stack[stack.length - 1]){
                stack.pop()
            }
            stack.push(max)
        } else {
            stack.push(item)
        }

    })
    return stack.length
};

时空复杂度

• 时间复杂度：O(N)
• 空间复杂度: O(Max(len(stackSize)))

[yunliuyan]

思路

设置一个栈，将数组的数字依次入栈 当入栈的元素比栈顶的元素大或者相等时，则开始入栈，表示它可以是新的一个块 当入栈的元素比栈顶的元素小时，则开始把栈里面元素出栈，直到栈顶的元素小于该元素(出栈的元素表示与该元素是一个块)

代码

function maxChunksToSorted(arr: number[]): number {
    const stack: number[] = [];
    for(const val of arr) {
        if (!stack.length || val >= stack[stack.length - 1]) {
            stack.push(val);
        } else {
            const blockMaxVal = stack.pop();
            // 大于当前值的都属于同一个块
            while(stack.length && stack[stack.length - 1] > val) {
                stack.pop();
            };
            stack.push(blockMaxVal);
        }
    }
    return stack.length;
};

时空复杂度

时间复杂度: O(n) 空间复杂度：O(1)

[MiumMi]

思路

1. 如果当前元素A比之前的元素B小，那么A跟B一定是成一块儿的（这样才能满足每个块排序之后拼接起来还是按升序排列的条件）；如果当前元素A比之前的元素B大或者相等的，那么A跟B是单独成块（这样满足最多块数的条件）
2. 根据以上条件，遍历数组，如果当前元素比栈顶大的或者相等的，直接入栈成为一个独立块儿（单增栈）

3. 如果当前元素比栈顶小的，说明跟当前元素是可以拼成一块儿的，则保留了当前栈的最大值作为栈顶，同时，比当前元素大的其他块要全部丢弃（单增栈原则）

   代码

   
   function maxChunksToSorted(arr: number[]): number {
   let stack = [];
   for(let i = 0; i < arr.length; i++){
       const temp = arr[i];
       if (!stack.length || temp >= stack[stack.length - 1]){
           stack.push(temp);
       } else {
           const max = stack.pop();
           while(stack.length && stack[stack.length - 1] > temp) {
               stack.pop();
           }
           stack.push(max);
       }
   }
   return stack.length;
   };

---
### 分析
1. 时间复杂度：O(n)
2. 空间复杂度：O(n)