Leetcode题解——30. 包含min函数的栈（辅助栈思想）

 题目地址：剑指 Offer 30. 包含min函数的栈 - 力扣（LeetCode）

目录

一.算法思想

二.代码实现

三.拓展思考

---

 

 

 首先说结论，这道题虽然难度不大，但是算法思想很重要，是辅助栈应用的生动实例。

所以，这里小编不再重点将代码，而是讲思想。

一.算法思想

本题使用了辅助栈的思想，小编私以为叫同步栈更加合适。

首先一个栈用来正常存放，记作st。

再设一个栈用来存放最小值，记作st_min。

这里的难点就是在st出栈后，假如出栈元素就是最小值，那么怎么回溯到上一个最小值。

本题的最核心的思想就是：

当st入栈出栈时，st_min同时入栈出栈。即同步栈。

但是st_min入栈的值始终是此时的最小值。

即，如果此时st入栈值小于st_min，那st_min入该值。

但如果st入栈值大，那st_min继续入自己的栈顶元素，即最小值。

以图举例：

此时st中入了三个元素，但后两个元素都比st_min的栈顶元素1大，所以st_min依旧入自己栈顶元素。 

但当-3入栈st后，-3小于1，所以st_min开始入栈-3。

出栈时就是正常出栈，当st中-2出栈，st_min也同步出栈-3。

这样就可以利用同步栈的特性，完美的解决了当出栈值就是最小值时，回溯到上一个最小值的问题。这也就是本题最核心的算法。 

二.代码实现

class MinStack {
     stack<int> st;
     stack<int> st_min;
public:
    MinStack() 
    {
        st_min.push(INT_MAX);//首先装入一个最大值，确保第一个入栈元素能入st_min
    }
    
    void push(int x) {
        st.push(x);
        if(x < st_min.top())
            st_min.push(x);
        else st_min.push(st_min.top());
    }
    
    void pop() {
       st.pop();
       st_min.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int min() {
        return st_min.top();
    }
};

三.拓展思考

小编感觉遇到栈和队列的问题，不妨多思考思考多个栈和多个队列组合、混合组合的方式。

这往往能用来解决问题。 

比如最经典的用栈实现队列 Loading Question... - 力扣（LeetCode）

用队列实现栈225. 用队列实现栈 - 力扣（LeetCode）

这些都是非常经典的算法思想启发题。 

在小编看来，解题最重要的不在难度，而是对于思想的启发。人是在创新中前进而不是在固步自封的强化中前进。

 

 拼命干活无法取代理解。—— H William

---

如有错误，敬请斧正