【Leetcode】155. 最小栈、JZ31 栈的压入、弹出序列

本是古典何须时尚 2024-03-22 19:45 50阅读 0赞

>  作者：小卢
> 
> 专栏：《Leetcode》
> 
> 喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
> 
> ![7d63d497b5114103b3dd7633a1ba4731.jpeg][]
> 
> --------------------

## 155. 最小栈 ##

[155. 最小栈][155.]

题目描述;

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

实现 MinStack 类:

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

示例：

![75f64b42086e47f98f239be906850f70.png][]

思路：

利用俩个栈，一个用了正常存储，一个用了存储最小值，遍历正常的栈，如果\_st的top小于等于\_minst的top,就将这个栈压进去，出栈的话也是类似

代码：

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

## JZ31 栈的压入、弹出序列 ##

[栈的压入、弹出序列\_牛客题霸\_牛客网][Link 1]

题目描述：

![7338adf3c3e74ab5a2638b0861b902b7.png][]

示例：

![8dbef79900b1467594762ae6627ccbaf.png][]

代码：

class Solution {
    public:
        bool IsPopOrder(vector<int> pushV,vector<int> popV) {
            stack<int>st;
            int pushi=0;
            int popi=0;
            while(pushi<pushV.size())
            {
                st.push(pushV[pushi++]);
                while(!st.empty()&&st.top()==popV[popi])
                {
                    st.pop();
                    popi++;
                } 
            }
            return popi==popV.size();
        }
    };

[7d63d497b5114103b3dd7633a1ba4731.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/cdfc9b07c2fe4436b3817b99c593e852.png
[155.]: https://leetcode.cn/problems/min-stack/
[75f64b42086e47f98f239be906850f70.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/bdc28d04eba94209a87100bd89f14a2b.png
[Link 1]: https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking#:~:text=%E4%B8%8B%E4%B8%80%E9%A2%98-,JZ31%20%E6%A0%88%E7%9A%84%E5%8E%8B%E5%85%A5%E3%80%81%E5%BC%B9%E5%87%BA%E5%BA%8F%E5%88%97,-%E9%A2%98%E7%9B%AE
[7338adf3c3e74ab5a2638b0861b902b7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/b4b48f6dfb8d482090b602ad61612b62.png
[8dbef79900b1467594762ae6627ccbaf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/478cfa8e7cc64db481f7933583ecbb05.png