时间戳

首页 > 技术文章 > 包含min函数的栈（Python and C++解法）

包含min函数的栈（Python and C++解法）

kongzimengzixiaozhuzi 2020-07-08 11:23 原文

题目：

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 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.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof

思路：

　　如果使用一个变量存储栈中的最小值，那么当前最小值弹出后，将将无法获得次小值。因此临时变量需要能够最小值、次小值、再次小值。

　　考虑使用辅助栈，如果新入栈的元素比辅助栈栈顶元素小，则也压入辅助栈；如果新入栈的元素比辅助栈栈顶元素大，则辅助栈应当压入辅助栈当前栈顶元素，以保证主栈弹出顶部非最小元素时，辅助栈弹出栈顶元素后仍然存有最小值。

　　python中栈是以列表为基础，和C++中的栈的操作不同。

Python解法：

 1 class MinStack:
 2 
 3     def __init__(self):
 4         """
 5         initialize your data structure here.
 6         """
 7         self.mainStack = []  # 主栈存储数据
 8         self.helpStack = []  # 辅助栈存储最小值
 9 
10     def push(self, x: int) -> None:
11         self.mainStack.append(x)
12         # 如果辅助栈为空或者新入栈的元素比辅助栈栈顶元素小，则新元素压入辅助栈
13         if len(self.helpStack) == 0 or self.helpStack[-1] > x:  # helpStack是列表基础，所以helpStack顶部元素是[-1]位置而不是[0]位置
14             self.helpStack.append(x)
15         else:  # 如果新入栈的元素比辅助栈栈顶元素大，则当前最小元素继续压入辅助栈，以免被弹出
16             self.helpStack.append(self.helpStack[-1])
17     
18     def pop(self) -> None:
19         if len(self.mainStack) != 0:
20             del self.mainStack[-1]
21             del self.helpStack[-1]
22 
23     def top(self) -> int:
24         return self.mainStack[-1]
25 
26     def min(self) -> int:
27         return self.helpStack[-1]

C++解法：

 1 class MinStack {
 2 public:
 3     /** initialize your data structure here. */
 4     stack<int> mainStack;
 5     stack<int> helpStack;
 6 
 7     MinStack() {    
 8     }
 9     
10     void push(int x) {
11         mainStack.push(x);
12         if (helpStack.empty() || helpStack.top() > x)
13             helpStack.push(x);
14         else
15             helpStack.push(helpStack.top());
16     }
17     
18     void pop() {
19         if (!mainStack.empty() && !helpStack.empty()) {
20             mainStack.pop();
21             helpStack.pop();
22         }
23     }
24     
25     int top() {
26         return mainStack.top();
27     }
28     
29     int min() {
30         return helpStack.top();
31     }
32 };

推荐阅读