Daily LeetCode – day0015 0768. Max Chunks To Make Sorted II

// 0768. Max Chunks To Make Sorted II
class Solution {
    public int maxChunksToSorted(int[] arr) {
        Stack<Block> stack = new Stack<>();
        stack.push(new Block(arr[0], arr[0]));
        for (int i = 1; i < arr.length; ++i) {
            if (arr[i] >= stack.peek().maxNum) {
                stack.push(new Block(arr[i], arr[i]));
            } else if (arr[i] < stack.peek().minNum) {
                Block insert = new Block(arr[i], stack.peek().maxNum);
                while (!stack.empty() && insert.minNum < stack.peek().maxNum) {
                    Block top = stack.pop();
                    if (insert.minNum > top.minNum) {
                        insert.minNum = top.minNum;
                    }
                }
                stack.push(insert);
            }
        }
        return stack.size();
    }
}

class Block {
    int minNum;
    int maxNum;

    Block(int minNum, int maxNum) {
        this.minNum = minNum;
        this.maxNum = maxNum;
    }
}

学习笔记：
这是一道有趣的困难题。
一开始我想到的解法是从左往右贪心+局部排序。但这样时间复杂度真的爆表。后来看了提示说用栈，然后就写了一个栈的。但是不知道为什么速度就是偏慢，别人应该用的是其它的思路。我用了面向对象的思路，内存还是特别省的。