建站
咨詢
售后
建站咨詢
新聞中心
前言
基于數(shù)據(jù)結(jié)構(gòu): “?！?，實(shí)現(xiàn)一個(gè)min函數(shù)，調(diào)用此函數(shù)即可獲取棧中的最小元素。在該棧中，調(diào)用min、push、pop的時(shí)間復(fù)雜度都是O(1)。
成都創(chuàng)新互聯(lián)公司聯(lián)系熱線：18982081108，為您提供成都網(wǎng)站建設(shè)網(wǎng)頁(yè)設(shè)計(jì)及定制高端網(wǎng)站建設(shè)服務(wù)，成都創(chuàng)新互聯(lián)公司網(wǎng)頁(yè)制作領(lǐng)域10年，包括成都水電改造等多個(gè)行業(yè)擁有多年的網(wǎng)站設(shè)計(jì)經(jīng)驗(yàn)，選擇成都創(chuàng)新互聯(lián)公司，為網(wǎng)站保駕護(hù)航。
思路梳理
相信大多數(shù)開(kāi)發(fā)者看到這個(gè)問(wèn)題，第一反應(yīng)可能是每次往棧中壓入一個(gè)新元素時(shí)，將棧里的所有元素排序，讓最小的元素位于棧頂，這樣就能在O(1)的時(shí)間內(nèi)得到最小元素了。但這種思路不能保證最后入棧的元素能夠最先出棧，因此這個(gè)思路行不通。
緊接著，我們可能會(huì)想到用一個(gè)變量來(lái)存放最小的元素，每次壓入一個(gè)新元素入棧時(shí)，如果它比當(dāng)前最小的元素還要小，則更新最小元素。這樣子做目的是達(dá)到了，但是又會(huì)有另一個(gè)問(wèn)題：如果當(dāng)前最小元素被彈出棧了，那么如何得到下一個(gè)最小的元素？
很顯然，我們僅僅添加一個(gè)變量用來(lái)存儲(chǔ)最小元素是不夠的，也就是說(shuō)當(dāng)最小元素被取出時(shí)，我們希望得到次最小元素。那么，我們能否用一個(gè)輔助棧專門(mén)來(lái)存放這些最小元素呢？當(dāng)元素入棧時(shí)，我們就取出輔助棧中的棧頂元素將其與新加入元素做大小比較，把較小的一方壓入輔助棧中。
我們通過(guò)一個(gè)例子來(lái)講解下這個(gè)過(guò)程，如下所示：
const stack = [
3,
5,
7
12,
1,
9,
0
]
入棧過(guò)程如下圖所示：
出棧時(shí)，我們同時(shí)彈出兩個(gè)棧的棧頂元素，獲取最小元素時(shí)，我們將輔助棧的棧頂元素返回即可，過(guò)程如下圖所示：
實(shí)現(xiàn)代碼
經(jīng)過(guò)前面的分析，我們已經(jīng)得出了完整的思路，接下來(lái)就是編碼環(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ì)此感興趣的開(kāi)發(fā)者請(qǐng)移步：數(shù)組實(shí)現(xiàn)棧與對(duì)象實(shí)現(xiàn)棧的區(qū)別
我們將上個(gè)章節(jié)的例子代入上述實(shí)現(xiàn)的函數(shù)中，來(lái)看下它能否正確運(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
當(dāng)前標(biāo)題：我們一起聊聊包含min函數(shù)的棧
地址分享：http://m.fisionsoft.com.cn/article/dpiojjg.html
