【C/C++】768. 最多能完成排序的块 II

---

题目链接：768. 最多能完成排序的块 II

题目描述

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

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

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

提示:

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

示例 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 的副本数组 sortArr，然后对其进行排序处理；
• 利用哈希表来记录两个数组中元素出现的频次，原数组 arr 出现的元素次数我们令其为 +1，那么拷贝的副本数组 sortArr 出现的元素次数我们令其为 -1；
• 在遍历两个数组的过程中，如果某个位置 i ∈ [0, n - 1] 使得原数组 arr 和拷贝数组 sortArr 每个元素出现的频次相同，那么就可以在此处进行分块处理。
• 使用哈希表对频次进行记录的同时，如果当某个元素的频次进行 ±1 时使得当前元素频次为 0，那么将其从哈希表中移除，那么当哈希表中的元素个数为 0 时，也就是可以进行分块的时候了。

复杂度分析

• 时间复杂度：单调栈 的解法时间复杂度为 O(n)O(n)O(n)，其中 n 是输入数组 arr 的长度。需要遍历一遍数组，入栈的操作最多为 n 次。排序 + 哈希表 的解法时间复杂度为 O(nlog⁡n)O(n \log n)O(nlogn)，其中 n 是输入数组 arr 的长度。排序需要消耗 O(nlog⁡n)O(n \log n)O(nlogn) 的时间复杂度，遍历一遍消耗 O(n)O(n)O(n) 的时间复杂度。
• 空间复杂度：单调栈的解法空间复杂度为 O(n)O(n)O(n)。栈的长度最多为 n，其中 n 是输入数组 arr 的长度。O(n)O(n)O(n)。排序完的数组和哈希表均需要消耗 O(n)O(n)O(n) 的空间复杂度。

代码实现

单调栈

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        // 单调栈
        stack<int> s; while(s.size()) s.pop();
        for(int &num : arr){
            // 当前 num 无需融入前一块
            if(s.empty() || s.top() <= num) s.push(num);
            else{
                // m 记录当前块最大值
                int m = s.top();
                while(!s.empty() && s.top() > num){
                    m = max(m, s.top());
                    s.pop();
                }
                // 利用 m 代表当前块
                s.push(m);
            }
        }
        return s.size();
    }
};

排序 + 哈希表

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        // 排序 + 哈希表
        unordered_map<int, int> mp; mp.clear();
        vector<int> sortArr = arr;
        sort(sortArr.begin(), sortArr.end());
        int n = arr.size(), ans = 0;
        for(int i = 0; i < n; i++){
            mp[arr[i]]++;
            if(mp[arr[i]] == 0) mp.erase(arr[i]);
            mp[sortArr[i]]--;
            if(mp[sortArr[i]] == 0) mp.erase(sortArr[i]);
            // 两个数组元素频次相同
            if(mp.size() == 0) ans++;
        }
        return ans;
    }
};

总结

• 排序 + 哈希表 的解法更容易理解，但是在时间复杂度上 单调栈 的解法更优，且在思维上单调栈解法更为巧妙，这里更推荐单调栈的解法，也是需要掌握的一种算法思维。
• 本题使用哈希表统计元素出现频次的方法很巧妙，在利用哈希表进行记录频次的同时，通过哈希表中元素个数来判断两个数组中元素出现频次是否相同。
• 单调栈的解法核心思想为：判断当前添加的数字是否大于或等于原数组最后一个块的最大值，来决定是否单独成块或者融入前一块，如果大于等于栈顶元素，则这个新添加的数字可以自己形成一个块。如果新添加的数字小于原数组最后一个块的最大值，则它必须融入栈顶所在的那一块。
• 测试结果：

通过测试对比，可以看出单调栈的解法在实际测试中确实是更优于排序+哈希表的解法。

结束语

人的成长就像植物一样有时间表，春种、夏长、秋收、冬藏，什么季节就干什么事。不必强求自己一定要在什么时间到达什么高度，但若想获得最好的收成，就应该在最好的时光里，汲取阳光和水分，扎根发芽、向上生长。新的一天，加油！