stack刷题

2023-12-20 22:41:49

最小栈

最小栈

设计一个支持?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();
    };
};

文章来源:https://blog.csdn.net/zyb___/article/details/135117767
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。