题目分析

这个题目，我们拿到之后，首先应该想到模拟，用给定的几个示例，模拟一下如何划分。

单调栈

我们想一下，如果大数出现在前面，小数出现在后面，结果一定不会很大。因为不将小数和大数放在同一个区间内，那么排列后的结果也一定是大数在小数前面，则不符合题目要求。因此我们得出一个结论，小数一定在大数前面。

如何保证小数一定出现在大数前面呢？答案很明显，我们要构造一个单调递增的栈，当出现小的元素时，需要将大的元素出栈。直到栈空或者栈中的元素都小于该元素，说明从栈中元素索引+1一直到该元素可以组成一个区间。

如栈是[0, 2]，2对应的索引是3，当前值是5，索引是6，说明从下标4一直到下标6可以构成一个符合条件的区间。

因此可以发现，存在多少个区间就等于单调栈中剩余多少个元素。

于是我就写出了如下算法，我心想这也太简单了吧，最多算一个中等题，怎么能算困难呢？

class Solution {
    public int maxChunksToSorted(int[] arr) {
        LinkedList<Integer> stack = new LinkedList<>();
        for (int x : arr) {
            if (stack.isEmpty() || stack.getLast() <= x) {
                stack.add(x);
            } else {
                int max = stack.pollLast();
                while (!stack.isEmpty() && stack.getLast() > x) {
                    stack.pollLast();
                }
                stack.add(max);
            }
        }
        return stack.size();
    }
}

刷题总结

单调栈的题目难度不算很大，但是变形题型比较多，希望小伙伴们多刷题，以后看到类似的题目才能灵光乍现。