【牛客JZ31】—栈的压入弹出序列判断算法详解

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

class Solution {
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        // 使用辅助栈模拟压栈弹栈过程
        stack<int> st;
        
        // 双指针：_push指向当前要压入的元素，_pop指向当前要弹出的元素
        size_t _push = 0;  // 压栈序列的索引
        size_t _pop = 0;   // 弹栈序列的索引
        
        // 遍历所有需要压入的元素
        while(_push < pushV.size()) {
            // 将当前元素压入栈中
            st.push(pushV[_push++]);
            
            // 检查栈顶元素是否与当前期望弹出的元素匹配
            // 如果匹配，则连续弹出所有匹配的元素
            while(!st.empty() && st.top() == popV[_pop]) {
                _pop++;      // 移动弹栈序列指针
                st.pop();    // 弹出栈顶元素
            }
        }
        
        // 如果所有元素都能正确弹出，栈应该为空
        return st.empty();
    }
};

// 初始状态
stack<int> st;        // 空栈
size_t _push = 0;     // 指向元素1
size_t _pop = 0;      // 指向元素4

// 压入元素1
st.push(1);           // 栈：[1]
_push = 1;            // 指向元素2

// 检查栈顶：1 != 4，不匹配，继续

// 压入元素2
st.push(2);           // 栈：[1, 2]
_push = 2;            // 指向元素3

// 检查栈顶：2 != 4，不匹配，继续

// 压入元素3
st.push(3);           // 栈：[1, 2, 3]
_push = 3;            // 指向元素4

// 检查栈顶：3 != 4，不匹配，继续

// 压入元素4
st.push(4);           // 栈：[1, 2, 3, 4]
_push = 4;            // 指向元素5

// 检查栈顶：4 == 4，匹配！
st.pop();             // 栈：[1, 2, 3]
_pop = 1;             // 指向元素5

// 压入元素5
st.push(5);           // 栈：[1, 2, 3, 5]
_push = 5;            // 超出范围

// 检查栈顶：5 == 5，匹配！
st.pop();             // 栈：[1, 2, 3]
_pop = 2;             // 指向元素3

// 继续检查：3 == 3，匹配！
st.pop();             // 栈：[1, 2]
_pop = 3;             // 指向元素2

// 继续检查：2 == 2，匹配！
st.pop();             // 栈：[1]
_pop = 4;             // 指向元素1

// 继续检查：1 == 1，匹配！
st.pop();             // 栈：[]
_pop = 5;             // 超出范围

// 主循环：遍历pushV中的每个元素
while(_push < pushV.size()) {  // O(n)
    st.push(pushV[_push++]);   // O(1)
    
    // 内层循环：每个元素最多被弹出一次
    while(!st.empty() && st.top() == popV[_pop]) {  // 总计O(n)
        _pop++;
        st.pop();
    }
}

stack<int> st;  // 辅助栈，最坏情况下存储所有元素

bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
    // 如果两个序列长度不同，直接返回false
    if (pushV.size() != popV.size()) {
        return false;
    }
    
    // 空序列的情况
    if (pushV.empty()) {
        return true;  // 两个空序列匹配
    }
    
    // 原算法逻辑...
}

// 测试用例
vector<int> pushV = {1};
vector<int> popV = {1};
// 结果：true

vector<int> pushV2 = {1};
vector<int> popV2 = {2};
// 结果：false