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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!