題?描述

定義棧的數據結構，請在該類型中實現?個能夠得到棧中所含最?元素的min 函數（時間復雜度為O（1） ）。

此棧包含的?法有：

• push(value) ：將value 壓?棧中
• pop() ：彈出棧頂元素
• top() ：獲取棧頂元素
• min() ：獲取棧中最?元素

思路及解答

雙棧法（推薦，實現簡單）

使用兩個棧：

1. ?主棧?：存儲所有元素
2. ?輔助棧?：存儲當前主棧中的最小值

push ?個元素的時候，都需要push 進datas stack ,但是push 進?mins stack 需要滿?條件：當前的mins stack 是空的，直接放?。或者當前的mins stack 的棧頂元素?于或者等于push 進來的值。

pop ?個元素的時候，如果棧為空則什么都不操作，如果棧不為空，則判斷datas 的第?個元素是否和mins 的第?個元素相等。如果相等的話那么就需要將mins 和datas pop 出去第?個元素，否則只需要將datas 的第?個元素 pop 出去即可。

public class Solution {
	private Stack<Integer> datas = new Stack<>();
	private Stack<Integer> mins = new Stack<>();

	/?**?
     * 將元素壓入棧中
     * @param value 要壓入的值
     */
	public void push(int node) {
		datas.push(node);
		// 如果輔助棧為空，或新值<=當前最小值，壓入輔助棧
		if (mins.isEmpty()) {
			mins.push(node);
		} else {
			int min = mins.peek();
			if (node <= min) {
				mins.push(node);
			}
		}
	}
	
	public void pop() {
		if (datas.isEmpty()) {
			return;
		} else {
			int value = datas.peek();
			if (value == mins.peek()) {
				mins.pop();
			}
			datas.pop();
		}
	}
	
	public int top() {
		if(datas.isEmpty()){
			return -1;
		}
		return datas.peek();
	}
	
	public int min() {
		if(mins.isEmpty()){
			return -1;
		}
		return mins.peek();
	}
}

• 時間復雜度： O(1)
• 空間復雜度： O(n) ,借助了輔助棧。

差值法

使用一個棧和一個變量minValue：

1. ?棧存儲差值?：存儲元素與當前最小值的差值
2. ?更新最小值?：當遇到更小值時，先存儲當前差值(負值)，再更新最小值
3. ?恢復前值?：pop時如果發現差值為負，說明此處發生過最小值更新，需要恢復前一個最小值

public class Solution {
    private Stack<Long> stack = new Stack<>();; // 存儲差值的棧
    private long minValue; // 當前最小值

    public void push(int value) {
        if (stack.isEmpty()) {
            minValue = value;
            stack.push(0L); // 差值為0
        } else {
            long diff = (long)value - minValue;
            stack.push(diff);
            // 如果差值為負，說明value是新的最小值
            if (diff < 0) {
                minValue = value;
            }
        }
    }

    public void pop() {
        if (stack.isEmpty()) {
            return;
        }
        long diff = stack.pop();
        // 如果差值為負，說明此處更新過最小值，需要恢復前一個最小值
        if (diff < 0) {
            minValue = minValue - diff;
        }
    }

    public int top() {
        if (stack.isEmpty()) {
           return;
        }
        long diff = stack.peek();
        // 如果差值為負，說明當前棧頂就是最小值
        if (diff < 0) {
            return (int)minValue;
        } else {
            return (int)(minValue + diff);
        }
    }

    public int min() {
        if (stack.isEmpty()) {
           return;
        }
        return (int)minValue;
    }
}

• 時間復雜度?：所有操作仍為O(1)
• ?空間復雜度?：O(1)額外空間（僅一個變量），但棧存儲的是差值而非原始值

需要考慮整數溢出問題（使用long存儲差值）