【算法题-困难】最多能完成排序的块

困难算法题，最多能完成排序的块，使用 JavaScript 语言编写

题目

给定一个整数数组 arr。将 arr 分割成若干块，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

返回能将数组分成的最多块数。

输入格式

1. 输入整数数列，元素之间以空格分开
2. 其中数组长度为n，1<=n<=1000,
3. 数组元素 1 <= arr[i], k <= 100，数组元素可有重复整数

输出格式

数组能分成的最多块数

输入样例

输入样例1：

5 4 3 2 1

输入样例2：

2 1 3 4 4

输出样例

输出样例1：

1

将数组分成2块或者更多块，都无法得到所需的结果。

例如，分成 [5, 4], [3, 2, 1] 的结果是 [4, 5, 1, 2, 3]，这不是有序的数组。

输出样例2：

4

可以把它分成两块，例如 [2, 1], [3, 4, 4]。

然而，分成 [2, 1], [3], [4], [4] 可以得到最多的块数。

代码长度限制

分析

解答

// 这是题目要求的输入格式
let inputs = `
0 2 3 1 4
`;

inputs = inputs.trim().split(' ').map(Number);

function maxChunksToSorted(arr) {
  // 初始化一个空栈 用来可以用来分成的块的最大的元素
  let stack = [];
  for (let i = 0; i < arr.length; i++) {
    const num = arr[i];
    if (stack.length && num < stack[stack.length - 1]) {
      // 需要合并块
      const tmp = stack.pop(); // 最大的数缓存起来
      // 把中间小于当前数的块都合并到这个块中来 
      // 举例：假设现在是[0,3,4]三个块，当碰到了元素1，1就需要跟3,4合并，剩下0,4两个块了
      while (stack.length && num < stack[stack.length - 1]) {
        stack.pop();
      }
      stack.push(tmp);
    } else {
      stack.push(num); //单独成块
    }
  }
  return stack.length;
}

console.log(maxChunksToSorted(inputs));


/**
    举例2 1 3 4 4
    第一趟 2 单独成一个块 stack: [2]
    第二趟 1小于2 所以 21单独成一个块 stack: [2, 1]
    第三趟 3大于2 单独成块 stack：[2, 1] [3]
    第四趟 4大于3 单独成块 stack: [2, 1] [3] [4]
    第五趟 4不小于4 单独成块 stack:  [2, 1] [3] [4] [4]
    结果就可以分成 [2, 1] [3] [4] [4] 总共四块

    举例0 2 3 1 4 
    第一趟 stack: [0]
    第二趟 stack: [0] [2]
    第三趟 stack: [0] [2] [3]
    第四趟 1小于3跟2，不小于0，132合并，剩下两个块 stack: [0] [1, 3, 2]
    第四趟 stack: [0] [1, 3, 2] [4]
    结果就分成了[0] [2,3,1] [4] 三个块
*/

解释