前言

基于數(shù)據(jù)結(jié)構(gòu): “?！保瑢?shí)現(xiàn)一個(gè)min函數(shù)，調(diào)用此函數(shù)即可獲取棧中的最小元素。在該棧中，調(diào)用min、push、pop的時(shí)間復(fù)雜度都是O(1)。

思路梳理

相信大多數(shù)開發(fā)者看到這個(gè)問題，第一反應(yīng)可能是每次往棧中壓入一個(gè)新元素時(shí)，將棧里的所有元素排序，讓最小的元素位于棧頂，這樣就能在O(1)的時(shí)間內(nèi)得到最小元素了。但這種思路不能保證最后入棧的元素能夠最先出棧，因此這個(gè)思路行不通。

緊接著，我們可能會(huì)想到用一個(gè)變量來存放最小的元素，每次壓入一個(gè)新元素入棧時(shí)，如果它比當(dāng)前最小的元素還要小，則更新最小元素。這樣子做目的是達(dá)到了，但是又會(huì)有另一個(gè)問題：如果當(dāng)前最小元素被彈出棧了，那么如何得到下一個(gè)最小的元素？

很顯然，我們僅僅添加一個(gè)變量用來存儲(chǔ)最小元素是不夠的，也就是說當(dāng)最小元素被取出時(shí)，我們希望得到次最小元素。那么，我們能否用一個(gè)輔助棧專門來存放這些最小元素呢？當(dāng)元素入棧時(shí)，我們就取出輔助棧中的棧頂元素將其與新加入元素做大小比較，把較小的一方壓入輔助棧中。

我們通過一個(gè)例子來講解下這個(gè)過程，如下所示：

const stack = [
  3,
  5,
  7
  12,
  1,
  9,
  0
]

入棧過程如下圖所示：

出棧時(shí)，我們同時(shí)彈出兩個(gè)棧的棧頂元素，獲取最小元素時(shí)，我們將輔助棧的棧頂元素返回即可，過程如下圖所示：

實(shí)現(xiàn)代碼

經(jīng)過前面的分析，我們已經(jīng)得出了完整的思路，接下來就是編碼環(huán)節(jié)了，如下所示：

export class StackContainingMinFunction extends Stack {
  private minStack: Stack;
  private dataStack: Stack;

  constructor() {
    super();
    this.minStack = new Stack();
    this.dataStack = new Stack();
  }

  public push(item: number): void {
    this.dataStack.push(item);
    if (this.minStack.size() > 0) {
      const minVal = this.minStack.peek();
      // 比較當(dāng)前入棧元素與minStack中的最小元素，將小的一方入minStack
      item > minVal ? this.minStack.push(minVal) : this.minStack.push(item);
      return;
    }
    this.minStack.push(item);
  }

  public pop(): void {
    this.minStack.pop();
    this.dataStack.pop();
  }

  public min(): number | null {
    if (this.minStack.size() > 0) return this.minStack.peek();
    return null;
  }
}

注意：上述代碼繼承了Stack，我們?cè)谥拔恼轮幸呀?jīng)實(shí)現(xiàn)了它，對(duì)此感興趣的開發(fā)者請(qǐng)移步：數(shù)組實(shí)現(xiàn)棧與對(duì)象實(shí)現(xiàn)棧的區(qū)別

我們將上個(gè)章節(jié)的例子代入上述實(shí)現(xiàn)的函數(shù)中，來看下它能否正確運(yùn)行。

const stackMinFn = new StackContainingMinFunction();
stackMinFn.push(3);
stackMinFn.push(5);
stackMinFn.push(7);
stackMinFn.push(12);
stackMinFn.push(1);
stackMinFn.push(9);
stackMinFn.push(0);
stackMinFn.pop();
stackMinFn.pop();
stackMinFn.pop();
console.log("當(dāng)前棧內(nèi)最小值為:", stackMinFn.min());

示例代碼

本文所列舉的代碼完整版請(qǐng)移步：

• StackContainingMinFunction.ts
• stackContainingMinFunction-test.ts