Min Stack

Question

  1. Implement a stack with min() function,
  2. which will return the smallest number in the stack.
  4. It should support push, pop and min operation all in O(1) cost.
  6. Example
  7. Operations: push(1), pop(), push(2), push(3), min(), push(1), min() Return: 1, 2, 1
  9. Note
  10. min operation will never be called if there is no number in the stack

题解

『最小』栈，要求在栈的基础上实现可以在 O(1) 的时间内找出最小值，一般这种 O(1)的实现往往就是哈希表或者哈希表的变体，这里简单起见可以另外克隆一个栈用以跟踪当前栈的最小值。

Java

  1. public class Solution {
  2.     public Solution() {
  3.         stack1 = new Stack<Integer>();
  4.         stack2 = new Stack<Integer>();
  5.     }
  7.     public void push(int number) {
  8.         stack1.push(number);
  9.         if (stack2.empty()) {
  10.             stack2.push(number);
  11.         } else {
  12.             stack2.push(Math.min(number, stack2.peek()));
  13.         }
  14.     }
  16.     public int pop() {
  17.         stack2.pop();
  18.         return stack1.pop();
  19.     }
  21.     public int min() {
  22.         return stack2.peek();
  23.     }
  25.     private Stack<Integer> stack1; // original stack
  26.     private Stack<Integer> stack2; // min stack
  27. }

源码分析

取最小栈的栈顶值时需要先判断是否为空栈(而不仅是 null)。

复杂度分析

均为 O(1).