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

https://leetcode-cn.com/problems/max-chunks-to-make-sorted-ii/

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

  • 题目描述

  • 方法 1: 滑动窗口

    • 思路

    • 复杂度分析

    • 代码 (JS/C++)

  • 方法 2: 单调栈

    • 思路

    • 图解

    • 复杂度分析

    • 代码(JS/C++)

题目描述

这个问题和“最多能完成排序的块”相似，但给定数组中的元素可以重复，输入数组最大长度为2000，其中的元素最大为10**8。

arr是一个可能包含重复元素的整数数组，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

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

示例 1:

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

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

arr的长度在[1, 2000]之间。
arr[i]的大小在[0, 10**8]之间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/max-chunks-to-make-sorted-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法 1: 滑动窗口

思路

题目有一个提示：

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

也就是原数组进行分块后，每一个分块和排序后的数组中对应的分块数字是一样的，只是排序不同。

既然每个分块中数字是一样的，那它们的和也是一样的了。我们可以用一个滑动窗口同时扫描原数组和排序数组，当窗口中数字的和一样时，就将数组进行分块，就像上图中的色块一样。

复杂度分析

• 时间复杂度：$O(NlogN)$，N 为数组长度，数组排序时间认为是 $NlogN$，滑动窗口遍历数组时间为 $N$。

• 空间复杂度：$O(N)$，N 为数组长度。

代码 (JS/C++)

JavaScript Code

/**
 * @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;
};

C++ Code

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;
    }
};

方法 2: 单调栈

思路

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

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

• 因为题目要求能分的最多的块数，所以我们在分块的时候要尽量把块分小，这样就能分得比较多。

• 在遍历数组的过程中，如果一个数字比之前所有分块的最大值都要大，我们就把它作为一个新的分块。

• 如果数字小于之前某些分块的最大值，那这些分块都要被合成一个分块(保持栈的单调递增)。

图解

再看一个例子：

复杂度分析

• 时间复杂度：$O(N)$，N 为数组长度。

• 空间复杂度：$O(N)$，N 为数组长度，单调栈消耗的空间。

代码(JS/C++)

JavaScript Code

class Stack {
  constructor() {
    this.list = [];
  }
  push(val) {
    this.list.push(val);
  }
  pop() {
    return this.list.pop();
  }
  empty() {
    return this.list.length === 0;
  }
  peek() {
    return this.list[this.list.length - 1];
  }
  size() {
    return this.list.length;
  }
}

/**
 * @param {number[]} arr
 * @return {number}
 */
var maxChunksToSorted = function (arr) {
  const stack = new Stack();

  for (let i = 0; i < arr.length; i++) {
    if (stack.empty() || stack.peek() <= arr[i]) {
      stack.push(arr[i]);
    } else {
      const temp = stack.pop();

      while (stack.peek() > arr[i]) {
        stack.pop();
      }

      stack.push(temp);
    }
  }
  return stack.size();
};

C++ Code

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        stack<int> blocks;

        for (int i = 0; i < arr.size(); i++) {
            if (blocks.empty() || blocks.top() <= arr[i]) {
                // a new chunk
                blocks.push(arr[i]);
            }
            else {
                int topNum = blocks.top();
                blocks.pop();

                // combine chunks
                while (!blocks.empty() && blocks.top() > arr[i]) {
                    blocks.pop();
                }
                blocks.push(topNum);
            }
        }

        return blocks.size();
    }
};