stack刷题

最小栈

最小栈

设计一个支持?push?，pop?，top?操作，并能在常数时间内检索到最小元素的栈。

实现?MinStack?类:

• MinStack()?初始化堆栈对象。
• void push(int val)?将元素val推入堆栈。
• void pop()?删除堆栈顶部的元素。
• int top()?获取堆栈顶部的元素。
• int getMin()?获取堆栈中的最小元素。

思路：使用两个栈，一个栈作为普通的栈，push、pop、top等操作；另一个栈，判断要 push的元素是否是栈中的最小值，是就 push。这保证了 第二个栈的栈顶元素永远就是堆栈中的最小元素。

pop 元素的时候，如果第二个栈的栈顶元素和第一个栈的栈顶元素相同时，再?pop 第二个栈的栈顶元素。

class MinStack {
public:
    MinStack() {}
    void push(int val) {
        st1.push(val);
        if(st2.empty() || val <= st2.top()) st2.push(val);
    }
    void pop() {
        if(st1.top()==st2.top()) st2.pop();
        st1.pop();
    }
    int top() {
        return st1.top();
    }
    int getMin() {
        return st2.top();
    }
    stack<int> st1;
    stack<int> st2;
};

栈的压入、弹出序列

栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

1.? 0<=pushV.length ==?popV.length <=1000

2.? -1000<=pushV[i]<=1000

3.? pushV?的所有数字均不相同

思路：模拟这个入栈、出栈序列

依次入栈，直到栈顶元素等于出栈序列的第一个元素，这时候就出栈，再次判断栈顶元素是否等于出栈序列的下一个元素，等于就出栈，直至不等于或栈为空时，继续入栈。

当入栈序列被遍历结束后，模拟入栈、出栈这个过程就结束了。判断出栈序列是否可以满足这个入栈序列：当栈最终为空时，说明出栈序列可以匹配入栈序列，返回 true，否则就是不匹配，返回 false。

class Solution {
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        // write code here
        int cur1 = 0,cur2 = 0, n = pushV.size();
        stack<int> st;
        while(cur1 < n)
        {
            st.push(pushV[cur1++]);
            while(!st.empty() && st.top() == popV[cur2])
            {
                st.pop();
                cur2++;                
            }
        }
        return st.empty();
    };
};