最小栈 与 栈的压入、弹出序列

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨ 🐻强烈推荐优质专栏: 🍔🍟🌯C++的世界(持续更新中) 🐻推荐专栏1: 🍔🍟🌯C语言初阶 🐻推荐专栏2: 🍔🍟🌯C语言进阶 🔑个人信条: 🌵知行合一 🍉本篇简介:>:记录两个有关栈的oj题

一、最小栈

题目来源于:力扣 题目链接:传送门

题目介绍:

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

实现 MinStack 类:

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

示例与解释:

输入：

[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”] [[],[-2],[0],[-3],[],[],[],[]]

输出:

[null,null,null,null,-3,null,0,-2]

解释：

MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.

解题思路

采用两个栈的方式. push_stack:用于正常的插入数据. min_stack:用于记录当前栈最小值.

此方法需要注意最小栈(min_stack)的及时更新.

当我们执行压栈push操作时: (1)min_stack:插入的第一个数据 或者 新插入的元素 < 当前栈的最小元素时,将待插入数据压栈. (2)push_stack:用于正常的插入数据.

当我们执行压栈pop操作时: (1) min_stack:如果删除的值==当前栈的最小值,则min_stack也要跟着删除. (2)push_stack:用于正常的删除数据.

top(): 返回 push_stack.top();即可.

getMin(): 返回min_stack.top();即可.

示例图:

代码实现:

class MinStack {
public:
    MinStack() {
       
    }
    
    void push(int val) {
    //第一个数据或者新插入的元素比当前栈的最小元素要小
        if((push_stack.size()==0) ||(min_stack.top() >= val))
        {
            min_stack.push(val);
        }
        push_stack.push(val);
    }
    
    void pop() {
    //如果删除的值是当前栈的最小值,则min_stack也要跟着删除
        if(push_stack.top()==min_stack.top()){
            min_stack.pop();
        }
        push_stack.pop();
       
    }
    
    int top() {
       return push_stack.top();
    }
    
    int getMin() {
        return min_stack.top();
    }
private:
    stack<int> push_stack; 
    stack<int> min_stack;
};

二、栈的压入、弹出序列

题目来源于:牛客 题目链接:传送门

题目介绍:

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个在这里插入代码片序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列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 的所有数字均不相同

示例:

输入：

[1,2,3,4,5],[4,5,3,2,1]

返回值：

true

解释： 可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop() 这样的顺序得到[4,5,3,2,1]这个序列，返回true

解题思路

既然我们要判断是否是一个栈的出栈序列,我们可以通过模拟栈的出栈这种方式来判断.

1. 创建一个栈,模拟进栈的过程.
2. 每次入栈一个数据以后,判断与出栈序列首个元素是否相同.
3. 不想同则表示此时不出栈,则继续入栈.
4. 相同则表示此时可以出栈,则一直出栈直到不相同.
5. 最后如果出栈序列走完了,则表明是正确的出栈序列.

代码实现

class Solution {
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        stack<int> push_satck;
        int j=0;
       for(int i=0;i<pushV.size();i++)
       {
            push_satck.push(pushV[i]);
            while(push_satck.size()>0 && push_satck.top()==popV[j])
            {
                push_satck.pop();
                j++;
            }  
       }
       // return j==popV.size();
       if(j==popV.size())
       {
        return true;
       }
       return false;
    }
};