题目

题目地址：

https://leetcode-cn.com/problems/min-stack/

题目描述：

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈（解题的关键）。

push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。

示例:

输入：

[“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”]

[[],[-2],[0],[-3],[],[],[],[]]

输出：

[null,null,null,null,-3,null,0,-2]

解释：

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin(); —> 返回 -3.

minStack.pop();

minStack.top(); —> 返回 0.

minStack.getMin(); —> 返回 -2.

提示：

  • pop、top 和 getMin 操作总是在 非空栈 上调用。（相当于告诉你操作这三个方法的时候不需要判断栈是否为空）

思路

题目要求需要能够在常数时间内检索到最小元素的栈，这个是解题的关键 , 我们可以考虑使用一个中间栈来存储最小值

放一张 LeetCode 题解的动图，就应该好理解了

LeetCode155. 最小栈 - 图1

测试用例


程序

时间复杂度：对于题目中的所有操作，时间复杂度均为 O(1)。因为栈的插入、删除与读取操作都是 O(1)，我们定义的每个操作最多调用栈操作两次。

空间复杂度：O(n)，其中 n 为总操作数。最坏情况下，我们会连续插入 n 个元素，此时两个栈占用的空间为 O(n)。

  1. class MinStack:
  3.     def __init__(self):
  4.         """
  5.         initialize your data structure here.
  6.         """
  7.         self.stack = []      
  8.         self.min_stack = [math.inf]
  10.     def push(self, x: int) -> None:              
  11.         self.min_stack.append(min(self.min_stack[-1], x))
  12.         self.stack.append(x)
  15.     def pop(self) -> None:
  16.         self.min_stack.pop(-1)
  17.         return self.stack.pop(-1)
  20.     def top(self) -> int:
  21.         return self.stack[-1]
  24.     def getMin(self) -> int:
  25.         return self.min_stack[-1]
  29. # Your MinStack object will be instantiated and called as such:
  30. # obj = MinStack()
  31. # obj.push(x)
  32. # obj.pop()
  33. # param_3 = obj.top()
  34. # param_4 = obj.getMin()