最小棧的實(shí)現(xiàn)與優(yōu)化

最小棧

實(shí)現(xiàn)一個(gè)最小棧，一步一步優(yōu)化，從額外空間O(N) 到O(1) 。面試官看重代碼邏輯。push,pop,top,getMin都是O(1)時(shí)間。

1 用一個(gè)最小棧來存儲(chǔ)最小值

1.1要點(diǎn)：

• 2個(gè)棧，data用來存儲(chǔ)數(shù)據(jù)，minValue用來存儲(chǔ)最小值。

• push時(shí)，data直接push數(shù)據(jù)；minValue直接放入當(dāng)前最小的值。（對(duì)于minValue有一個(gè)優(yōu)化，當(dāng)push的數(shù)據(jù)比當(dāng)前最小值大的時(shí)候，我們可以不對(duì)minValue進(jìn)行最小值的插入；如果小于或者等于最小值，就需要把最新的最小值push入棧minValue。

• pop時(shí)，data直接pop出數(shù)據(jù)；同時(shí)，更新minValue，更新的策略是與push中的優(yōu)化對(duì)應(yīng)的策略——pop出的數(shù)，如果==當(dāng)前的最小值，就需要把minValue進(jìn)行pop一次。

• getMin：直接返回棧minValue 的 top元素即可。

• top: 直接返回棧data的top元素即可。

1.2 復(fù)雜度和代碼

額外空間消耗O(N)，如何優(yōu)化到O(1).

public class MinStack1 {    private Stack<Integer> data = new Stack<Integer>();    private Stack<Integer> minValue = new Stack<Integer>();    public void push(int x) {
        data.push(x);        if (minValue.isEmpty() || x <= minValue.peek())
            minValue.push(x);
    }    public void pop() {        int value = data.pop();        if (value == minValue.peek())
            minValue.pop();
    }    public int top() {        return data.peek();
    }    public int getMin() {        return minValue.peek();
    }
}

2 優(yōu)化空間復(fù)雜度到O(1)

如何只用一個(gè)棧實(shí)現(xiàn)最小棧的實(shí)現(xiàn)？

• 棧不能夠只存儲(chǔ)原始數(shù)據(jù)，應(yīng)該存儲(chǔ)差值。

• 用一個(gè)變量來計(jì)算棧的最小值

• 用簡單的示例來探索思路。

2.1 圖

入棧順序：2,1,3,4,-2,0,-2
diff棧的計(jì)算 = data - min

top : 如何根據(jù)diff棧來恢復(fù)棧頂top的元素？
push : 如何更新min最小值？
pop : 如何維護(hù)min的最小值？

2.2 代碼

注意：第一次入棧diff的特殊處理。

public class MinStack3 {    private Stack<Integer> diff = new Stack<Integer>();    private int minValue;    public void push(int x) {        if (diff.isEmpty()) {
            minValue = x;
            diff.push(0);
        } else {            int compare = x - minValue;
            diff.push(compare);
            minValue = compare < 0 ? x : minValue;
        }
    }    public void pop() {        int top = diff.peek();
        minValue = top < 0 ? (minValue - top) : minValue;
        diff.pop();
    }    public int top() {        int top = diff.peek();        return top > 0 ? top + minValue : minValue;
    }    public int getMin() {        return minValue;
    }
}

新航道雅思