我們一起聊聊包含min函數的棧

作者：神奇的程序員 2022-09-07 07:27:36

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

前言

基于數據結構: “棧”，實現一個min函數，調用此函數即可獲取棧中的最小元素。在該棧中，調用min、push、pop的時間復雜度都是O(1)。

思路梳理

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

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

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

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

入棧過程如下圖所示：

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

實現代碼

經過前面的分析，我們已經得出了完整的思路，接下來就是編碼環節了，如下所示：

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();
      // 比較當前入棧元素與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，我們在之前文章中已經實現了它，對此感興趣的開發者請移步：數組實現棧與對象實現棧的區別

我們將上個章節的例子代入上述實現的函數中，來看下它能否正確運行。

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("當前棧內最小值為:", stackMinFn.min());

示例代碼

本文所列舉的代碼完整版請移步：

StackContainingMinFunction.ts
stackContainingMinFunction-test.ts

責任編輯：武曉燕來源：神奇的程序員

函數棧元素