力扣768-最多能完成排序的块2

摘要: 双指针+哈希表、单调栈两种解法的问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文我们来看一个一题多解的问题：力扣 768。第一种解法是单调栈，不过此前我们解决过的单调栈的问题，栈里保存的都是下标，而本题保存的是值；第二种是双指针+哈希表。下面我们来看这个题。

---

$1 题目

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

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

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

注意:

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

示例 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] 可以得到最多的块数。

$2 题解

算法1: 尺取法+unordered_multiset

记原数组为 arr，排序后的数组为 sorted。

用 i, j 维护尺取法。

在 i 处，判断 arr[i] 在 sorted 中的位置 idx。

• 若 idx <= i，则 arr[i] 自己是一块。
• 否则记 maxx = arr[i], sorted[iter..idx-1] 插入 setting，然后从 j = i + 1 开始推进 j 直到 setting 变空。

在推进 j 的过程中，在用 iter 表示 sorted 中的位置，arr[i..j] 在 sorted 中的位置总是小于 iter。取 i 对应的区间开始时，iter = i，取完 i 对应的区间时，iter = j。

推进 j 的时候，考察 arr[j]。

• 如果 arr[j] < maxx，删除 setting 元素。
• 如果 arr[j] == maxx，++iter 记录
• 如果 arr[j] > maxx，arr[j] 在 sorted 中的位置为 idx。将 sorted[iter..idx-1] 插入 setting

代码 (C++)

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int n = arr.size();
        int i = 0;
        unordered_multiset<int> setting;
        vector<int> sorted = arr;
        sort(sorted.begin(), sorted.end());
        int ans = 0;
        while(i < n)
        {
            int idx = lower_bound(sorted.begin(), sorted.end(), arr[i]) - sorted.begin();
            if(idx <= i) // 此时应该有 i == iter
            {
                ++ans;
                ++i;
                continue;
            }
            for(int k = i; k < idx; ++k)
                setting.insert(sorted[k]);
            int maxx = arr[i];
            int iter = idx + 1;
            int j = i + 1;
            while(j < n && !setting.empty())
            {
                if(arr[j] < maxx)
                    setting.erase(setting.find(arr[j]));
                else if(arr[j] == maxx)
                    ++iter;
                else
                {
                    int idx = lower_bound(sorted.begin(), sorted.end(), arr[j]) - sorted.begin();
                    for(int k = iter; k < idx; ++k)
                        setting.insert(sorted[k]);
                    iter = idx + 1;
                    maxx = arr[j];
                }
                ++j;
            }
            // 此时应该有 j == iter
            ++i;
            ++ans;
            i = j;
        }
        return ans;
    }
};

算法2: 单调栈

枚举 i，在栈里始终维护各个临时块的最大值，如果栈顶小于等于 a，则直接压 arr[i] 进栈，它自己是一个临时块，否则需要弹栈。

所有最大值大于 i 的临时块都要与 i 合并。合并的过程是不断弹出栈顶直至栈顶小于 arr[i]，过程中维护弹出值的最大值，最后将 maxx 压会栈，表示合并后的新的临时块。

枚举完成后栈里的元素个数就是块的个数。

代码 (C++)

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        stack<int> st;
        for(int a: arr)
        {
            int maxx = a;
            while(!st.empty() && st.top() > a)
            {
                maxx = max(st.top(), maxx);
                st.pop();
            }
            st.push(maxx);
        }
        return st.size();
    }
};

---