題目描述:
定義棧的數(shù)據(jù)結(jié)構(gòu)，請在該類型中實現(xiàn)一個能夠得到棧最小元素的min函數(shù)。
分析：
發(fā)現(xiàn)現(xiàn)在的題目都有點言簡意賅但是韻味雋永的感覺，我本來以為這就是一道很平常的題目，但是仔細查了下，這是一道Google06年的面試題，那么也就是說，這道題目的考察點還是很全面很有價值的。
首先，要求函數(shù)min、push以及pop的時間復(fù)雜度都是O(1)。
我們考慮在原本要求的棧之外新開一個棧，用來記錄最小值，當原棧push數(shù)據(jù)后，與最小值棧中的棧頂元素比較，如果新值比較小，則在最小值棧中push新值，否則繼續(xù)push最小值棧的棧頂元素。這樣，pop的時候，只要將最小值棧也pop一下就可以了。而min函數(shù)返回最小值棧的棧頂元素即可。
如上的常規(guī)解法，需要額外的線性空間。具體實現(xiàn)的代碼如下：
代碼：
import java.util.Stack;
public class Solution {
private Stack<Integer> stack = new Stack<>();
private Stack<Integer> minStack = new Stack<>();
public void push(int node) {
stack.push(node);
minStack.push(minStack.isEmpty()?node:Math.min(minStack.peek(),node));
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int min() {
return minStack.peek();
}
}
優(yōu)化：
常規(guī)解空間上的一個優(yōu)化:
一般說來,最小值不會每次都需要更新,因此最小值棧里面會有很多重復(fù)元素.因此一個簡單的優(yōu)化就是：在新值當且僅當<=原最小值時，才pushIntoMin，注意這個==的條件是不可少的，這是為了防止在pop的時候錯誤的pop最小值。pop時, 當待pop值==最小值時，popMinStack, 其他時候不對最小值棧進行pop。
下面說一種具有常數(shù)空間復(fù)雜度的方法:
在這個方法里,只需要額外開一個用于存放當前最小值的變量min即可.因此下面提到的push和pop操作都是對于題目中要求的棧來操作的,當然,這也是這個算法里唯一的棧.
設(shè)push的參數(shù)為v_push,pop的返回值為v_pop.
先說下整體思路:因為棧中所有元素的值都不會小于當其為棧頂元素時min函數(shù)的值,所以在棧中其實只需要保存某元素比相應(yīng)最小值大出來的值就可以了.而對于最小值更新的位置,棧元素肯定為0,因此可以利用這個位置來保存更多的信息,在這里是更新后前兩個最小值的差值,而這個值肯定是非正的.
根據(jù)上面的思路,push函數(shù)按照如下策略進行:
首先push (v_push-min),如果v_push < min,更新min為v_push.
相應(yīng)的,pop函數(shù)按照如下策略進行(稱棧頂元素為top):
如果top >= 0, v_pop = min+top, 如果top < 0, v_pop = min,然后更新min為min-top.
顯然,對于min函數(shù)來說,只需要返回min空間的內(nèi)容即可.
與張霄學長交流后,學長也講了一個類似的方法:
push時候 如果 v_push >= min, v_push 直接入棧， 如果 v_push < min, 那么入棧的是 2 * v_push - min, 然后 min = v_push. 出棧時， 如果棧頂?shù)膖op >= min 直接出，如果 top < min 則出現(xiàn)異常，將min作為pop的返回值，另外需要還原前一個最小值，方法是 min = 2 * min - top
其實這兩種方法在思路上是完全一樣的,只是學長提供的方法里,棧中所有元素都比我的方法里大v_push.不過,這種變化直接帶來的好處是,在不更新最小值的情況下,壓棧值和出棧值都不需要額外的計算,在高級語言層面上,一次加減法運算比單純的賦值至少多了一次訪存操作和一次alu的運算,這樣估計來我的方法耗時會是學長方法的2倍左右,雖然時間復(fù)雜度都是一樣的.
