【面试经典150 | 栈】最小栈

Tag

【设计类】【栈】

题目来源

155. 最小栈

题目解读

本题是一个设计类的题目，设计一个最小栈类 MinStack() 实现：

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

解题思路

方法一：辅助栈

维护两个栈，一个栈就是常规的栈 stk1，另一个栈 stk2 用来存放已经插入栈 stk1 中数字的最小值。

注意入栈和出栈操作时两个栈都要更新。

实现代码

class MinStack {public:MinStack() {min_stk.push(INT_MAX);}void push(int val) {stk.push(val);min_stk.push(std::min(min_stk.top(), val));}void pop() {stk.pop();min_stk.pop();}int top() {return stk.top();}int getMin() {return min_stk.top();}private:std::stack<int> stk;std::stack<int> min_stk;
};/*** 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();*/

复杂度分析

时间复杂度：$O(1)$。

空间复杂度：$O(n)$，$n$ 为 操作次数。

方法二：一个栈

可以只使用一个栈来同时保存当前的最小值和 val。

实现代码

class MinStack {
private:stack<pair<int, int>> stk;
public:MinStack() {stk.push(make_pair(INT_MAX, INT_MAX));}void push(int val) {stk.push({min(stk.top().first, val), val});}void pop() {stk.pop();}int top() {return stk.top().second;}int getMin() {return stk.top().first;}
};/*** 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();*/

复杂度分析

时间复杂度：$O(1)$。

空间复杂度：$O(1)$。

方法三：栈中存放差值

现在我们维护一个变量 minVal，表示当前插入的变量的最小值，栈中每次入栈的是 val 与 minVal 的差值 differ。现在进行具体分析：

• push(int val)：如果此时栈为空，我们更新 minVal = val，向栈中插入 0；如果此时栈非空，首先向栈中插入 diff，根据 diff 的值来更新 minVal：
  • 如果 diff > 0，说明插入的 val 大于当前的 minVal，则 minVal 不需要更新；
  • 否则表明插入的 val 小于或者等于当前的 minVal，则更新 minVal = val。
• pop()：我们需要根据 diff 来更新弹出栈顶元素后的 minVal，具体地：
  • 先弹出栈顶元素 diff，并 pop；
  • 如果 diff > 0，说明我们当时插入的 val 大于当时的 minVal，则 minVal 是不需要更新的；
  • 否则说明当时插入的 val 小于或者等于 minVal，当时的 minVal 是插入的 val，需要将 minVal 还原回去，即当时插入 val 更新 minVal 的过程如下，还原回去得到 minVal = minVal + diff。

$$diff=val-minVal;minVal=val;$$

• top()：如果 diff < 0，表示 minVal 就是最小栈的栈顶元素，否则 minVal + diff 才是最小栈的栈顶元素。
• getMin()：直接返回 minVal 即可。

实现代码

class MinStack {
private:stack<long long> stk;long long minVal, diff;
public:MinStack() {}void push(int val) {if (stk.empty()) {stk.push(0);minVal = val;}else {diff = val - minVal;stk.push(diff);minVal = diff > 0 ? minVal : val;}}void pop() {diff = stk.top();stk.pop();if (diff < 0) {minVal = minVal - diff;}}int top() {return stk.top() < 0 ? minVal : minVal + stk.top();}int getMin() {return minVal;}
};/*** 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();*/

复杂度分析

时间复杂度：$O(1)$。

空间复杂度：$O(1)$。

其他语言

python3

以下只给出方法三的 python3 代码，该方法比较巧妙，值得好好研究。

class MinStack:def __init__(self):"""initialize your data structure here."""self.stack = []def push(self, x: int) -> None:if not self.stack:self.stack.append(0)self.min_value = xelse:diff = x-self.min_valueself.stack.append(diff)self.min_value = self.min_value if diff > 0 else xdef pop(self) -> None:if self.stack:diff = self.stack.pop()if diff < 0:self.min_value = self.min_value - diffdef top(self) -> int:return self.min_value if self.stack[-1] < 0 else self.stack[-1] + self.min_valuedef getMin(self) -> int:return self.min_value if self.stack else -1

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。