【OJ】stack刷题

zxctscl

发布于 2024-04-10 09:18:11

730

发布于 2024-04-10 09:18:11

文章被收录于专栏：zxctscl个人专栏zxctscl个人专栏

题目

1. 155. 最小栈
- 1.1 分析
- 1.2 代码
2. JZ31 栈的压入、弹出序列
- 2.1 分析
- 2.2 代码
3. 150. 逆波兰表达式求值
- 3.1 分析
- 3.2 代码

1. 155. 最小栈

1.1 分析

利用两个栈，一个栈a负责入数据和出数据，另一个_min负责放存入数据中目前最小的数。如果_min中没有数据，那么a入数据的时候，它也入。但是_min里面放的是a中目前最小的数据，所以如果数据小于_min的top所放的数据时也插入。那么相等时候的的数据_min插不插入呢？

当然val和_min.top()数据相同时候也插入。因为再删除数据的时候，当a栈顶出栈的时候,_min栈顶同时也得出栈，这样才能保证_min.top()里面能够保存的是最小值。所以pop得这样写：

  void pop() {
        if(a.top()==_min.top())
        {       
            _min.pop();
        }
        a.pop();
    }

题目要求返回最小值，那么就是返回_min.top()：

    int getMin() {
       return _min.top();
    }

1.2 代码

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

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

2. JZ31 栈的压入、弹出序列

2.1 分析

这里用了两个栈，想要匹配出栈的顺序，最简单的方法就是：先把入栈序列入栈，如果出现入栈序列和出栈序列的栈顶元素相同，那么两边就同时出数据，直到入栈序列和出栈序列的栈顶元素不匹配，或者出栈序列为空。想要知道最后匹不匹配就直接判断一下入栈序列是否为空。为空就是已经匹配，否则就不匹配。

2.2 代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型vector 
     * @param popV int整型vector 
     * @return bool布尔型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        // write code here
          int pushi=0,popi=0;
          stack<int> st;
          while(pushi<pushV.size())
          {
            st.push(pushV[pushi++]);
            while(!st.empty()&&st.top()==popV[popi])
            {
                ++popi;
                st.pop();
            }
          }
          return st.empty();

    }
};

3. 150. 逆波兰表达式求值

3.1 分析

逆波兰表达式就是后缀表达式，而我们一般用的是中缀表达式。举个例子：把中缀表达式换成后缀表达式

用例1来分析一下：

在没有遇到第一个算符之前，就把数据入栈，当遇到运算符，就把它前面两个数2和1出，计算出来结果就是2+1=3，然后再把这个3再入栈；当再一次遇到表达式时候，又把它的前面两个数出栈做对应的运算之后，在把算出的结果入栈，最后输出栈顶元素就可以了。

3.2 代码

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        set<string> s={"+","-","*","/"};
        for(auto&str:tokens)
        {
            if(s.find(str)!=s.end())
            {
                int right=st.top();
                st.pop();
                int left=st.top();
                st.pop();
                switch(str[0])
                {
                    case '+':
                         st.push(left+right);
                         break;
                    case '-':
                         st.push(left-right);
                         break;
                    case '*':
                         st.push(left*right);
                         break;
                    case '/':
                         st.push(left/right);
                         break;
                }
            }
            else{
                st.push(stoi(str));
            }
        }
     return st.top();
    }
   
};

有问题请指出，大家一起进步！！!

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-04-07，如有侵权请联系 cloudcommunity@tencent.com 删除

min