【leetcode】【2022/8/13】768. 最多能完成排序的块 II

问题描述：

• arr 是一个可能包含重复元素的整数数组，将这个数组分割成几个“块”，并将这些块分别进行排序，之后再连接起来，使得连接的结果和按升序排序后的原数组相同。
  • 返回最多能将数组分成的块数。
  • 输入数组最大长度为 2000，其中的元素最大为 10**8。

核心思路：

• 该题虽然是困难题，但暴力解题思路并不难想出。【思路很多样，可以用不同的方法来解】
  • 由问题描述可以知道，将数组分成块 1 和 块 2，则块 2 中任一元素必然大于块 1 中所有元素。
• 方法一相当于暴力法，维护一个与数组大小相等的并查集，在向后的单次遍历中，每步都向前线性搜索，只要遇到比当前数 arr[i] 更大的数 arr[j]，就将两个索引进行合并 union(i, j)。
  • 核心代码如下：【该方法就是创建一个普通并查集（并查集在实现上并无特别），之后就实施遍历，最后返回并查集中的集合个数】

    for(int i = 0; i < m; ++i) for(int j = i-1; j >= 0; --j)
    {
      if(arr[j] > arr[i])
        uf.union(i, j); // uf 为 unionfind
    }
    1
    2
    3
    4
    5

  • 遍历完成后，并查集中的集合个数就相当于是需要返回的数组分块数。
  • 该方法相当于是模拟了分块过程，不断往前面已访问的子数组添加数值，一旦新添数值低于前面子数组的某个数值，就需要合并到前面的某个块中。
• 方法二是将数组 arr 进行排序（用另一数组 sorted 保存排序后结果），同时遍历排序前后的两个数组进行比较。【比较当前遍历遇到过的字符是否频数相等，如果频数相等，则块数加一】
  • 相当于滑动窗口思想中判断窗口中信息是否满足条件，关键在于如何判断频数相等。
  • 判断频数相等的方法又有很多：哈希表计数、前缀数组累加。
• 方法三相当于方法一模拟分块的优化版本，利用了单调栈思想。
  • 方法一中提到了：一旦新添数值低于前面子数组的某个数值，就需要进行合并块。
  • 可以看出块与块之间整体是单调递增的，也就是说最后生成的块与块之间，块提取出来的最大值集合是单调递增的。
  • 由此可以舍弃并查集维护块结构的想法，而利用单调栈来维护块的信息，如前所述，就是用单调栈维护块的最大值。
  • 具体来说，从前往后遍历数组，只要当前访问数值 arr[i] （即新添数值）比单调栈中的栈顶 stk.top() 更大，则可直接入栈（即形成一个新块）；若 arr[i] < stk.top()，则弹出栈顶保存（注意要保存，后续要弹入该值，这里相当于把倒数第一个块弹出），接着将 arr[i] 与栈中剩余元素比较（这里相当于把新添数值与倒数第二个块、倒数第三个块进行比较），不断出栈数值上更高的栈顶，直到遇到一个块的最大值不高于 arr[i]（相当于找到一个可融合的块），此时 arr[i] 入栈并将原先保存的第一个块的最大值入栈。【结合代码进行理解即可】
  • 访问结束后，栈中元素个数也就是分块数。
• 方法四相当于方法二的优化版本，左边块中最大值需要低于右边的元素，则可以放弃排序做法，而改用维护前缀最大值数组和后缀最小值数组。
  • 整个思路类似于接雨水（leetcode 42 题）。
  • 建立好前缀数组和后缀数组之后，一次遍历即可，只要当前位置下 prefix_max[i] <= suffix_min[i+1]，则可以将块数加一。

代码实现：

• 排序 + 前缀和方法代码实现如下：【贴自评论区】

  int maxChunksToSorted(vector<int>& arr) {
    vector<int> res = arr;
    sort(res.begin(), res.end());
    int num = 0;
      long sum1 = 0, sum2 = 0;
    for (int i = 0; i < arr.size(); i++)
    {
      sum1 += res[i];
      sum2 += arr[i];
      if (sum1 == sum2) num++;
    }
    return num;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13

• 排序 + 哈希表计数方法代码实现如下：

  class Solution
  {
  public:
      int maxChunksToSorted(vector<int>& arr)
      {
          vector<int> sorted = arr;
          sort(sorted.begin(), sorted.end());
  
          int ans = 0;
          unordered_map<int, int> cnt; // 记录两个数组的频数差值
          for(int i = 0; i < arr.size(); ++i)
          {
              ++cnt[sorted[i]];
              --cnt[arr[i]];
              if(cnt[sorted[i]] == 0)
                  cnt.erase(sorted[i]);
              if(cnt[arr[i]] == 0)
                  cnt.erase(arr[i]);
              if(cnt.empty())
                  ++ans;
          }
          return ans;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24

• 单调栈方法代码实现如下：【贴自官方题解】

  class Solution {
  public:
      int maxChunksToSorted(vector<int>& arr) {
          stack<int> st;
          for (auto &num : arr) {
              if (st.empty() || num >= st.top()) { // 自成一块
                  st.emplace(num);
              } else { // 需要融入前面的某个块，注意到最后 num 是不入栈的
                  int mx = st.top();
                  st.pop();
                  while (!st.empty() && st.top() > num) { // 找到可融入的块
                      st.pop();
                  }
                  st.emplace(mx);
              }
          }
          return st.size();
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19

• 前缀 + 后缀方法代码实现如下：

  class Solution
  {
  public:
      int maxChunksToSorted(vector<int>& arr)
      {
          int m = arr.size();
          vector<int> prefix_max(m);
          vector<int> suffix_min(m);
          prefix_max[0] = arr[0];
          for(int i = 1; i < m; ++i)
              prefix_max[i] = max(prefix_max[i-1], arr[i]);
          suffix_min[m-1] = arr[m-1];
          for(int i = m-2; i >= 0; --i)
              suffix_min[i] = min(suffix_min[i+1], arr[i]);
          
          int ans = 1;
          for(int i = 0; i < m-1; ++i)
          {
              if(prefix_max[i] <= suffix_min[i+1])
                  ++ans;
          }
          return ans;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24