最小棧的實現與優化

最小棧

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

1 用一個最小棧來存儲最小值

1.1要點：

• 2個棧，data用來存儲數據，minValue用來存儲最小值。

• push時，data直接push數據；minValue直接放入當前最小的值。（對于minValue有一個優化，當push的數據比當前最小值大的時候，我們可以不對minValue進行最小值的插入；如果小于或者等于最小值，就需要把最新的最小值push入棧minValue。

• pop時，data直接pop出數據；同時，更新minValue，更新的策略是與push中的優化對應的策略——pop出的數，如果==當前的最小值，就需要把minValue進行pop一次。

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

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

1.2 復雜度和代碼

額外空間消耗O(N)，如何優化到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 優化空間復雜度到O(1)

如何只用一個棧實現最小棧的實現？

• 棧不能夠只存儲原始數據，應該存儲差值。

• 用一個變量來計算棧的最小值

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

2.1 圖

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

top : 如何根據diff棧來恢復棧頂top的元素？
push : 如何更新min最小值？
pop : 如何維護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;
    }
}

新航道雅思