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

解题思路

本题是一道特殊的数据结构设计问题，要求我们设计出一个包含 stack.min() 方法的栈，并且要求 min，push，pop 这些方法的时间复杂度均为 O(1)

我的思路为，在这个最小栈中维护两个栈，一个是正常的实现存储数据功能的栈，命名为 dataStack，还有一个是专门用来维护此时栈中最小的元素的栈，命名为 minStack，该栈的栈顶始终存储栈中最小的元素。

当我们向栈中压入一个数据时，dataStack 正常执行 push 操作；minStack 则是要比较压入的数据与栈顶元素的大小，如果新压入的数据比栈顶元素大，那么我们就将栈顶元素复制一份压入至 minStack 中，如果新压入的数据比栈顶元素小，那么我们就压入新的数据到 minStack 中，这样做的目的是时时维护 minStack 栈顶的元素是当前数据栈中最小的元素。

出栈操作就比较简单了，我们只需让 dataStack 和 minStack 同步出栈即可。

代码

  1. class MinStack {
  3.     private Stack<Integer> dataStack;
  4.     private Stack<Integer> minStack;
  6.     /** initialize your data structure here. */
  7.     public MinStack() {
  8.         dataStack = new Stack<>();
  9.         minStack = new Stack<>();
  10.     }
  12.     public void push(int x) {
  14.         if(dataStack.isEmpty()){
  15.             dataStack.push(x);
  16.             minStack.push(x);
  17.         }else {
  18.             dataStack.push(x);
  19.             if(minStack.peek() < x){
  20.                 minStack.push(minStack.peek());
  21.             }else {
  22.                 minStack.push(x);
  23.             }
  24.         }
  25.     }
  27.     public void pop() {
  28.         minStack.pop();
  29.         dataStack.pop();
  30.     }
  32.     public int top() {
  33.         return dataStack.peek();
  34.     }
  36.     public int min() {
  37.         return minStack.peek();
  38.     }
  39. }
  41. /**
  42.  * Your MinStack object will be instantiated and called as such:
  43.  * MinStack obj = new MinStack();
  44.  * obj.push(x);
  45.  * obj.pop();
  46.  * int param_3 = obj.top();
  47.  * int param_4 = obj.min();
  48.  */

复杂度分析

  • 时间复杂度：O(1)

push(),pop(),top(),min() 四种操作的时间复杂度均为 O(1)

  • 空间复杂度：O(N)

我们使用的辅助栈 minStack 使用了 O(N) 的额外空间