每日算法：最小棧（包含getMin函數(shù)的棧）

設(shè)計(jì)一個(gè)支持 push ，pop ，top 操作，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧。

• push(x) —— 將元素 x 推入棧中。
• pop() —— 刪除棧頂?shù)脑亍?/section>
• top() —— 獲取棧頂元素。
• getMin() —— 檢索棧中的最小元素。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

解答在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧，即僅需保證 getMin 的時(shí)間復(fù)雜度為 O(1) 即可

class MinStack {
  constructor () {
    this.length = 0;
    this.content = [];
    this.mins = [];
  }
  push (val) {
    const curMin = this.mins[this.length - 1] !== undefined ? this.mins[this.length - 1] : Infinity;
    this.content[this.length++] = val;
    this.mins[this.length - 1] = Math.min(curMin, val);
  }
  pop () {
    return this.content[--this.length]
  }
  top () {
    return this.content[this.length - 1]
  }
  getMin () {
    return this.mins[this.length - 1];
  }
}

時(shí)間復(fù)雜度：進(jìn)棧O(1)，出棧O(n)，獲取棧頂元素O(1)，獲取最小元素O(1)

空間復(fù)雜度：O(n)