【栈】栈的最小值（面试题 03）

一、题目

请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。
执行push、pop和min操作的时间复杂度必须为O(1)。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/min-stack-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

  

 

  
1
  
2
  
3
  
4
  
5
  
6
 

二、分析

我们都知道，对于栈来说，没有现成的函数getMin()来实现获取栈中元素的最小值。为此，需要我们自己来实现一个getMin()。当然，简单的做法是：遍历栈中的元素，通过比较来获取栈中元素的最小值，这样一来，时间复杂度就是O(n)。

对于本题而言，需要保证getMin()的时间复杂度必须为O(1)，所以以上方法不可取。本着空间换时间的基本思想，我们可以创建一个辅助栈min_stack，来存储最小值，并始终放在栈顶。这样就可以直接通过min_stack.top()来直接获取栈的最小值，时间复杂度满足O(1)的要求！

三、题解

根据以上的分析，通过C++实现如下：

class MinStack {
public: /** initialize your data structure here. */ stack<int> x_stack; stack<int> min_stack; MinStack() { min_stack.push(INT_MAX); } void push(int x) { x_stack.push(x); min_stack.push(min(min_stack.top(),x)); } void pop() { x_stack.pop(); min_stack.pop(); } int top() { return x_stack.top(); } int getMin() { return min_stack.top(); }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
 

文章来源: ai-wx.blog.csdn.net，作者：AI 菌，版权归原作者所有，如需转载，请联系作者。

原文链接：ai-wx.blog.csdn.net/article/details/118574266