剑指 Offer | 30. 包含min函数的栈

「爱情、让人受尽委屈。」 2023-01-01 10:53 105阅读 0赞

**题目：**

> 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是  
> O(1)。

**示例:**

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

**提示：**

各函数的调用总次数不超过 20000 次

--------------------

**思路：**

*  一个栈存放所有元素，另一个辅助栈存储当前状态下的最小值。

**代码：**

class MinStack { 
    public:
        /** initialize your data structure here. */
        stack<int> data, help;
        MinStack() { 
    
        }
        
        void push(int x) { 
            data.push(x);
            // 如果x是data和help的第一个元素，或者x小于等于help的最小元素，入栈
            if(help.empty() || x <= help.top()) help.push(x);
            if(x > help.top())
            { 
                // 如果x大于help的最小元素，向help中再压入一遍该最小元素，保持两个栈元素个数相等
                // 比如data里现在有3，help里现在也有3，data里压入一个4，那么help里压入一个3
                // 这样如果把data的4弹出，我们同步把help的3也弹出
                int temp = help.top();
                help.push(temp);
            }
        }
        
        void pop() { 
            if(!data.empty() && !help.empty())
            { 
                data.pop();
                help.pop();
            }
        }
        
        int top() { 
            return data.top();
        }
        
        int min() { 
            return help.top();
        }
    };
    
    /** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(x); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->min(); */

参考：[字节题库 - \#剑30 - 简单 - 包含min函数的栈 - 1刷][- _30 - _ - _min_ - 1]

哎，啥时候自己也可以写出精彩的题解…

[- _30 - _ - _min_ - 1]: https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/solution/zi-jie-ti-ku-jian-30-jian-dan-bao-han-minhan-shu-d/