768.最多能完成排序的块2

768. 最多能完成排序的块 II

题目描述：

$ arr $ 一个包含重复元素的数组，将该数组分成几块，并在块内排序，然后将块连接起来，使得得到的结果和按照升序排列之后的数组相同。最多能将数组分为多少块？

数据范围：
$ arr_i <= 10^8, n <= 2000 $

题解：

首先有多种方法可以做。右边块的最小值大于等于左边块的最大值。依次遍历元素，如果比左侧最大元素大，可以形成一个新的块；如果比左侧最大元素小，可以与该区块合并，然后继续查看前一个区块，直到找到一个区块的最大值小于等于该元素。这个区块右边的所有区块合并，记录该区块的最大值。

这样的话可以使用单调栈，使用一个单调增栈，栈内元素一直递增表示不同区块的最大值，单调栈的大小就是答案。

还可以使用前缀和的做法，由于前缀和是单调增的，可以先对 $ arr $ 排序，然后求前缀和。当前缀和相等时，就增加一个区块。

代码：

class Solution
{
public:
    int a[2010];
    int top = -1;
    int maxChunksToSorted(vector<int> &arr)
    {
        int ans = 0;
        for (int i = 0; i < arr.size(); ++i)
        {
            // 单调增
            int maxx = arr[i];
            while (top != -1 && a[top] > arr[i])
            {
                maxx = maxx > a[top] ? maxx : a[top];
                top--;
            }
            a[++top] = maxx;
        }
        return top + 1;
    }
};