Link to LeetCode Problem

S1: 滑动窗口+贪心

题目有一个提示：

<aside> 💡 Each k for which some permutation of arr[:k] is equal to sorted(arr)[:k] is where we should cut each chunk.

</aside>

提示的意思是：如果将原数组进行分块，再将排序数据进行相同的分块，每个对应的分块中数字种类是相同的，仅仅是数字的排序不同。

既然每个分块中拥有的数字是一样的，那数字的和也是一样的。

我们可以用一个滑动窗口同时扫描原数组和排序数组，当窗口中包括的数字和一样时，贪心地进行分块（滑动窗口就是下图的色块）。

至于为什么要用到贪心，是因为题目问的是**我们最多能将数组分成多少块？**要获得尽量多的分块，那分块的大小就要尽量小，所以能分块的时候就要分块。

https://camo.githubusercontent.com/85ea23d35174577a3d5e586432d6e520aa9e7582a78cf0c133389b8090ea849f/68747470733a2f2f63646e2e6a7364656c6976722e6e65742f67682f7375756b69692f39312d646179732d616c676f726974686d2f6173736574732f30362e6d61782d6368756e6b732d746f2d6d616b652d736f727465642d69692d30302e706e67

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int n = arr.size();
        vector<int> sorted = arr;
        sort(sorted.begin(), sorted.end());

        long int arrSum = 0;
        long int sortedSum = 0;
        int chunkCount = 0;

        for (int i = 0; i < n; i++) {
            arrSum += arr[i];
            sortedSum += sorted[i];
            if (arrSum == sortedSum) chunkCount++;
        }

        return chunkCount;
    }
};

/**
 * @param {number[]} arr
 * @return {number}
 */
var maxChunksToSorted = function (arr) {
  const sorted = [...arr];
  sorted.sort((a, b) => a - b);

  let count = 0,
    sum1 = 0,
    sum2 = 0;

  for (let i = 0; i < arr.length; i++) {
    sum1 += arr[i];
    sum2 += sorted[i];

    if (sum1 === sum2) {
      count++;
      sum1 = sum2 = 0; // 这行不要也可以啦
    }
  }

  return count;
};

S2: 单调栈

根据题意，将原数组进行分块后，对各分块分别进行排序后的结果等于原数组排序后的结果。

可以得到的一个结论是，每个分块中的数字相对于前一个分块都是递增的(因为有重复数字，所以也可能是相同)，第 i+1 个分块中的所有数字会大于等于 第 i 个分块中的所有数字。