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

题目

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

单调栈解法复现：输入 [1,1,0,0,1]

让我们一步步复现单调栈解法在输入 [1,1,0,0,1] 时的执行过程：

1. 处理第一个元素 1

• 栈操作：栈为空，直接压入 1。
• 栈状态：[1]
• 块划分：当前块为 [1]，最大值为 1。

2. 处理第二个元素 1

• 比较：1 == 栈顶(1)，满足 num >= st.top()。
• 栈操作：直接压入 1。
• 栈状态：[1, 1]
• 块划分：新增块 [1]，最大值为 1。
• 当前块序列：[1], [1]

3. 处理第三个元素 0

• 比较：0 < 栈顶(1)，触发合并逻辑：
  1. 弹出栈顶 1，记录 maxVal = 1。
  2. 栈非空，且 st.top() = 1 > 0，继续弹出。
  3. 弹出 1 后，栈空，退出循环。
  4. 压入 maxVal = 1。
• 栈状态：[1]
• 块划分：合并块 [1, 1, 0]，最大值为 1。
• 当前块序列：[1, 1, 0]

4. 处理第四个元素 0

• 比较：0 < 栈顶(1)，触发合并逻辑：
  1. 弹出栈顶 1，记录 maxVal = 1。
  2. 栈空，退出循环。
  3. 压入 maxVal = 1。
• 栈状态：[1]
• 块划分：合并块 [1, 1, 0, 0]，最大值为 1。
• 当前块序列：[1, 1, 0, 0]

5. 处理第五个元素 1

• 比较：1 == 栈顶(1)，满足 num >= st.top()。
• 栈操作：直接压入 1。
• 栈状态：[1, 1]
• 块划分：新增块 [1]，最大值为 1。
• 最终块序列：[1, 1, 0, 0], [1]

最终结果

• 栈大小：2
• 最优划分：[1, 1, 0, 0], [1]
• 块数：2

关键分析

1. 合并逻辑的触发：
   当遇到 0 时，由于 0 < 1，需要将前面的块合并，确保块的最大值单调递增。否则，若保留 [1], [1], [0]，排序后 0 会出现在 1 前面，导致错误。

2. 保留最大值的意义：
   合并后压入 maxVal = 1，确保后续块的最大值必须 >=1，从而保证排序后整体有序。例如，若第五个元素是 2，则可形成新块 [2]，最终块序列为 [1, 1, 0, 0], [2]。

3. 验证排序结果：

   • 每个块内部排序：[0, 0, 1, 1], [1]。
   • 连接后：[0, 0, 1, 1, 1]，与原数组排序结果一致。

代码复现

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int maxChunksToSorted(vector<int>& arr) {
    stack<int> st;
    
    for (int num : arr) {
        cout << "处理元素: " << num << ", 栈状态: ";
        // 打印当前栈
        vector<int> temp;
        stack<int> copy = st;
        while (!copy.empty()) {
            temp.push_back(copy.top());
            copy.pop();
        }
        for (int i = temp.size() - 1; i >= 0; i--) {
            cout << temp[i] << " ";
        }
        cout << endl;
        
        if (st.empty() || num >= st.top()) {
            st.push(num);
            cout << "  压入 " << num << endl;
        } else {
            int maxVal = st.top();
            st.pop();
            cout << "  弹出 " << maxVal << ", 记录 maxVal = " << maxVal << endl;
            
            while (!st.empty() && st.top() > num) {
                cout << "  继续弹出 " << st.top() << endl;
                st.pop();
            }
            
            st.push(maxVal);
            cout << "  压入 maxVal = " << maxVal << endl;
        }
    }
    
    return st.size();
}

int main() {
    vector<int> arr = {1, 1, 0, 0, 1};
    cout << "最终块数: " << maxChunksToSorted(arr) << endl;
    return 0;
}

运行上述代码可观察到每一步的栈变化，验证整个处理过程。