leetcode

• 剑指 Offer 30. 包含min函数的栈
• • 题目
  • 代码
• 剑指 Offer 31.剑指 Offer 31. 栈的压入、弹出序列
• • 题目
  • 代码

class MinStack {
public:
    
    //注意此处定义栈
    stack stk;
    //增加一个辅助栈，思考何时将何数压入辅助栈中
    stack stkhelp;
    MinStack() {
    }
    void push(int x) {
        stk.push(x);
        //如果辅助栈为空，该值就是最小值，直接压入
        if(stkhelp.empty()) {
            stkhelp.push(x);
        }else {
            //如果x大于辅助栈栈顶元素，再压入一次当前最小值（即辅助栈栈顶值）
            if(x > stkhelp.top()) {
                stkhelp.push(stkhelp.top());
            }else {
                stkhelp.push(x);
            }
        }
    }
    
    void pop() {
        int value = stk.top();
        stk.pop();
        stkhelp.pop();
    }
    
    int top() {
        return stk.top();
    }
    
    int min() {
        return stkhelp.top();
    }
};

class Solution {
public:
    bool validateStackSequences(vector& pushed, vector& popped) {
        //剑指Offer的思路：如果弹出序列的下一个数字不是栈顶元素，那么在剩下的压入序列中找
        //找一个压一个入栈，直到压入序列到末尾都没有找到，那么就返回false
        //这里感觉是换了个判断的方向，遍历pushed序列入栈，如popped序列中当前数字等于栈顶元素，弹出  
        //栈顶元素,popped向下遍历，pushed压入序列操作完成后，如果此时栈为空，那么返回true
        stackstk;
        int sz1 = pushed.size();
        int sz2 = popped.size();
        int i = 0;
        for(auto a:pushed) {
            stk.push(a);
            while(!stk.empty() && stk.top() == popped[i]) {
                stk.pop();
                i++;
            }
        }
        if(stk.empty()) {
            return true;
        }
        return false;
    }
};