题目链接：https://leetcode-cn.com/problems/min-stack/
难度：简单

描述：
设计一个支持push，pop，top操作，并能在常数时间内检索到最小元素的栈。
实现MinStack类:

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

提示：

  • pop、top和getMin操作总是在非空栈上调用

题解

思路：
我们维持两个栈，一个普通栈存放元素，另一个栈存放最小元素。
当元素推入栈中时，若元素比栈中最小元素小，则同样将该元素推入最小栈中，否则将最小栈的栈顶元素复制后推入栈中。这样最小栈栈顶总是普通栈中的最小元素
当弹出元素时，弹出普通栈和最小栈中的元素。

  1. class MinStack:
  3.     def __init__(self):
  4.         self.stk = []
  5.         self.min_stk = []
  7.     def push(self, val: int) -> None:
  8.         if not self.stk:
  9.             self.stk.append(val)
  10.             self.min_stk.append(val)
  11.         else:
  12.             self.stk.append(val)
  13.             if val < self.min_stk[-1]:
  14.                 self.min_stk.append(val)
  15.             else:
  16.                 self.min_stk.append(self.min_stk[-1])
  18.     def pop(self) -> None:
  19.         self.min_stk.pop()
  20.         self.stk.pop()
  22.     def top(self) -> int:
  23.         return self.stk[-1]
  25.     def getMin(self) -> int:
  26.         return self.min_stk[-1]