快捷導航

前端算法之TypeScript包含min函數(shù)的棧實例詳解

更新時間：2022年09月26日 10:16:42 作者：神奇的程序員

這篇文章主要為大家介紹了前端算法之TypeScript包含min函數(shù)的棧實例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

前言

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

本文就跟大家分享下這個算法，歡迎各位感興趣的開發(fā)者閱讀本文。

思路梳理

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

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

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

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

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

入棧過程如下圖所示：

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

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

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

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