包含min函式的堆疊-有解無憂

目標：定義堆疊的資料結構，請在該型別中實作一個能夠得到堆疊的最小元素的 min 函式在該堆疊中，呼叫 min、push 及 pop 的時間復雜度都是 O(1)，

設計思路： 我們要做的是在我們每次資料入堆疊的時候，記錄當前資料堆疊中最小值，并且在pop()出堆疊之后依然能找到最小值；

　　　　方案①，如果只用一個 min 變數來保存每次入堆疊時候的最小值，那么出堆疊的時候，當前的最小值還是堆疊中的最小值嗎？假設堆疊中的資料按入堆疊順序依次為[ 2, 3, 5, 1 ] ，很明顯此時記錄的min值為1，那么當我們pop()出一條資料之后，堆疊變為 [ 2, 3, 5 ] ,此時的最小值應為2，但是記錄的min值為1，最小值記錄已丟失，此方案不通，

　　　　方案②，基于方案①的問題，我們應該設計一個結構，能夠保存我們每一步入堆疊的時候情況下的當前最小值，可能我們會想到用陣列結構排序后取最小值，但是要保證時間復雜度為O(1)，那么陣列結構方案舍棄（沒有一種陣列排序為O(1)復雜度），

　　　　方案③，在這里我采用堆疊結構來保存記錄最小值，為什么采用堆疊呢，堆疊結構有一個特點是保護現場和恢復現場的功能，想象一下，每次我們資料入堆疊時保存最小值，出堆疊的時候還要能恢復上一次的最小值，是不是和堆疊的這個特點不謀而合呢，所以我們采用堆疊結構，當然，在這里我們需要使用雙倍的存盤空間來實作功能，以空間換取時間╮(╯▽╰)╭，

首先我們實作一個Stack結構，代碼如下：

 1 class Stack {
 2     constructor() {
 3         this.stack = []
 4     }
 5     push(v) {
 6         this.stack.push(v)
 7     }
 8     pop() {
 9         this.stack.pop()
10     }
11     isEmpty() {
12         return !this.count()
13     }
14     count() {
15         return this.stack.length
16     }
17     top() {
18         return this.stack[this.count() - 1]
19     }
20 }

接著實作最小堆疊代碼

 1 class MinStack {
 2     data_stack = new Stack() // 存放真正的堆疊資料
 3     min_stack = new Stack() // 存放最小值堆疊
 4     constructor() { }
 5     push(val) {
 6         const min_stack = this.min_stack;
 7         // 資料入堆疊
 8         this.data_stack.push(val);
 9         /* 在最小堆疊中記錄每一次更新堆疊的當前情況下的最小值，
10         即保證最小堆疊堆疊頂始終記錄的是當前資料堆疊中最小的那個值，
11         那么在每次pop的時候，最小堆疊堆疊頂記錄的依舊記錄的是最小值，
12         就不用擔心第二小值的問題啦 */
13         if (min_stack.isEmpty() || val < min_stack.top()) {
14             min_stack.push(val)
15         } else {
16             min_stack.push(min_stack.top())
17         }
18     }
19     pop() {
20         this.data_stack.pop()
21         this.min_stack.pop()
22     }
23     min() {
24         return this.min_stack.top()
25     }
26 }

測驗結果

完整代碼如下

class Stack {
    constructor() {
        this.stack = []
    }
    push(v) {
        this.stack.push(v)
    }
    pop() {
        this.stack.pop()
    }
    isEmpty() {
        return !this.count()
    }
    count() {
        return this.stack.length
    }
    top() {
        return this.stack[this.count() - 1]
    }
}

class MinStack {
    data_stack = new Stack() // 存放真正的堆疊資料
    min_stack = new Stack() // 存放最小值堆疊
    constructor() { }
    push(val) {
        const min_stack = this.min_stack;
        // 資料入堆疊
        this.data_stack.push(val);
        /* 在最小堆疊中記錄每一次更新堆疊的當前情況下的最小值，
        即保證最小堆疊堆疊頂始終記錄的是當前資料堆疊中最小的那個值，
        那么在每次pop的時候，最小堆疊堆疊頂記錄的依舊記錄的是最小值，
        就不用擔心第二小值的問題啦 */
        if (min_stack.isEmpty() || val < min_stack.top()) {
            min_stack.push(val)
        } else {
            min_stack.push(min_stack.top())
        }
    }
    pop() {
        this.data_stack.pop()
        this.min_stack.pop()
    }
    min() {
        return this.min_stack.top()
    }
}

const min_stack = new MinStack()

min_stack.push(2)
console.log(min_stack.min());
min_stack.push(3)
console.log(min_stack.min());
min_stack.push(5)
console.log(min_stack.min());
min_stack.push(1)
console.log(min_stack.min());
min_stack.pop()
console.log(min_stack.min());

MinStack

@ 回傳主頁萍2櫻釋 ?( ′???` )

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/14521.html

標籤：其他

上一篇：0154. Find Minimum in Rotated Sorted Array II (H)

下一篇：CF 1368D AND, OR and square sum