题目

实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

要求

1pop、push、 getHin操作的时间复杂度都是O（1）
2设计的栈类型可以使用现成的栈结构。

题目意义

有一个栈，经常push，pop，还经常获取这个栈中的最小值。
获取栈的最小值方法，需要运行时间。如果使用冒泡算法，该时间是O(n)。
优化这个时间，最好是O(1)，那么需要以空间换时间。
那就用两个栈，一个栈是原有栈，另一个栈是对应的最小值栈。

最小值栈

每次原有栈push数据的同时，生成最小值push到最小值栈。
pop也一起pop。
这就保持了最小值的同步。

java版本示例代码

public class MyStack2 {
  private Stack<Integer> stackData;
  private Stack<Integer> stackMin;
  public MyStack2() {
    this.stackData = new Stack<Integer>();
    this.stackMin = new Stack<Integer>();
  }
  public void push(int newNum) {
    if (this.stackMin.isEmpty()) {
      this.stackMin.push(newNum);
    } else if (newNum < this.getmin()) {
      this.stackMin.push(newNum);
    } else {
      int newMin = this.stackMin.peek();
      this.stackMin.push(newMin);
    }
    this.stackData.push(newNum);
  }
  public int pop() {
    if (this.stackData.isEmpty()) {
      throw new RuntimeException("Your stack is empty.");
    }
    this.stackMin.pop();
    return this.stackData.pop();
  }
  public int getmin() {
    if (this.stackMin.isEmpty()) {
      throw new RuntimeException("Your stack is empty.");
    }
    return this.stackMin.peek();
  }
}

js版本示例代码

class myStack {
    constructor() {
        this.stackData = [];
        this.stackMin = [];
    }
    push(newNum) {
        var stackMin = this.stackMin;
        if (stackMin.length === 0) {
            stackMin.push(newNum);
        }
        else if (newNum < this.getmin()) {
            stackMin.push(newNum);
        }
        else {
            const newMin = stackMin[stackMin.length - 1];
            stackMin.push(newMin);
        }
        this.stackData.push(newNum);
    }
    pop(){
        if(this.stackData.length === 0){
            throw 'Your stack is empty'
        }
        this.stackMin.pop();
        return this.stackData.pop();
    }
    getmin() {
        let stackMin = this.stackMin;
        let len = stackMin.length;
        if (len === 0) {
            throw 'Your stack is empty'
        }
        return stackMin[len - 1];
    }
}

let mystack = new myStack();
mystack.push(1);
mystack.push(2);
mystack.push(1);
mystack.push(3);
mystack.push(0);

console.log(mystack.getmin());

mystack.pop();
console.log(mystack.getmin());