【Day 6 】2023-11-21 - 768. 最多能完成排序的块 II

[larscheng]

https://leetcode-cn.com/problems/max-chunks-to-make-sorted-ii/ https://github.com/leetcode-pp/91alg-12-daily-check/issues/7

[larscheng]

思路

• 数组拆分 => 局部升序 => 合并所有子序列 => 与原数组升序一致

要保证最终合并后的序列整体升序，那么拆分出来的数组块之间，必须要为递增趋势

• [2,1,3,4,4] 可拆分为 [2, 1], [3, 4, 4] , 第1块的中所有数组整体都小于第2块
• [2,1,3,4,4] 可拆分为 [2, 1], [3], [4], [4], 可见数组块之间整体递增趋势 题目要求最大可拆分数，第二种符合条件

结合单调栈：找下一个大于xxx、下一个小于xxx的思路.
保证最终留在栈内的都是每一轮寻找的最大值，栈的大小即为最大拆分块数

单调栈：栈内元素有序，出栈顺序升序为单调递增栈，出栈顺序降序为单调递减栈.

构造单调栈的过程：https://lucifer.ren/blog/2020/11/03/monotone-stack/ （推荐配合食用）

代码

class Solution {
    public int maxChunksToSorted(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        for (int num : arr) {
            if (stack.isEmpty() || stack.peek() <= num){
                stack.push(num);
            }else {
                int max = stack.pop();
                while (!stack.isEmpty() && stack.peek() > num) {
                    stack.pop();
                }
                stack.push(max);
            }
        }
        return stack.size();
    }
}

复杂度

• 时间复杂度：O(n)，数组中的元素最多只会入栈出栈1次，n为数组长度
• 空间复杂度：O(n)，额外空间栈的大小即为数组长度n