jz30.md

剑指 Offer 30. 包含min函数的栈

来源：力扣（LeetCode）

题目

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

解题思路

• 栈的push操作 -> 数组的push，符合数据复杂度O(1)

• 栈的pop操作 -> 数组的pop，符合数据复杂度O(1)

• 栈的min函数：

  • 方法1：计算栈中所有数据的最小指，时间复杂度O(n)，不符合要求；
  • 方法2：使用数组缓存所有的最小值，每次入栈时计算最小值（当前值和前一个最小值的min）并存入最小值数组。数据出栈时，由于栈是后进先出，之前数据的不变，最小值也不变，存储最小值数组也出栈即可。每次min操作时，取最小值数组的最后一个值。时间复杂度为O(1)

  JavaScript 源码

  code