769.max-chunks-to-make-sorted.md

数组 arr 是[0, 1, ..., arr.length - 1]的一种排列，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

我们最多能将数组分成多少块？

示例 1:

输入: arr = [4,3,2,1,0]
输出: 1
解释:
将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。
示例 2:

输入: arr = [1,0,2,3,4]
输出: 4
解释:
我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。
然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。

注意:

• arr 的长度在 [1, 10] 之间。
• arr[i]是 [0, 1, ..., arr.length - 1]的一种排列。

---

自洽

• 由于数组元素的特殊性，即数组 arr 是[0, 1, ..., arr.length - 1]的一种排列，
• 可以推导出分割后的块中的最大值 == 当前块的右边下标，能够分割成的块的个数 == 满足上述关系的最大值的个数。

代码实现

var maxChunksToSorted = function (arr) {
  if (arr.length == 0) return 0;
  let counter = 0,
    max = arr[0];
  for (let i = 0; i < arr.length; ++i) {
    if (arr[i] > max) max = arr[i];
    if (max == i) counter++;
  }
  return counter;
};

单调递增栈

算法思路

根据题意，我们可以推导出任何 每一段序列的最小值和最大值 [min1, max1], [min2, max2], [min3, max3]...

满足关系 min1 < max1 < min2 < max2 < min3 < max3 < ...

我们可以定义栈结构，维护上面的数列关系，代码如下：

代码实现

/**
 * @param {number[]} arr
 * @return {number}
 */
var maxChunksToSorted = function (arr) {
  if (arr.length == 0) return 0;
  let stack = [];
  stack.push([arr[0], arr[0]]);
  for (let i = 1; i < arr.length; i++) {
    let cur = stack[stack.length - 1];
    // 判断三者大小关系 arr[i], cur[0], cur[1]
    if (arr[i] > cur[1]) {
      stack.push([arr[i], arr[i]]);
    } else if (arr[i] < cur[0]) {
      let max = cur[1];
      while (arr[i] < cur[0]) {
        stack.pop();
        if (stack.length == 0) {
          stack.push([arr[i], max]);
          break;
        }
        cur = stack[stack.length - 1];
      }
      if (arr[i] > cur[1]) {
        stack.push([arr[i], max]);
      } else {
        stack.push([stack.pop()[0], max]);
      }
    }
  }
  return stack.length;
};