題目描述:
定義棧的數(shù)據(jù)結(jié)構(gòu)雏亚，請?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧最小元素的min函數(shù)。
分析：
發(fā)現(xiàn)現(xiàn)在的題目都有點(diǎn)言簡意賅但是韻味雋永的感覺摩钙，我本來以為這就是一道很平常的題目罢低，但是仔細(xì)查了下，這是一道Google06年的面試題，那么也就是說网持，這道題目的考察點(diǎn)還是很全面很有價(jià)值的宜岛。
首先，要求函數(shù)min功舀、push以及pop的時(shí)間復(fù)雜度都是O(1)萍倡。
我們考慮在原本要求的棧之外新開一個(gè)棧，用來記錄最小值辟汰，當(dāng)原棧push數(shù)據(jù)后列敲，與最小值棧中的棧頂元素比較，如果新值比較小帖汞，則在最小值棧中push新值戴而，否則繼續(xù)push最小值棧的棧頂元素。這樣翩蘸，pop的時(shí)候所意，只要將最小值棧也pop一下就可以了。而min函數(shù)返回最小值棧的棧頂元素即可催首。
如上的常規(guī)解法扶踊，需要額外的線性空間。具體實(shí)現(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ī)解空間上的一個(gè)優(yōu)化:
一般說來,最小值不會每次都需要更新,因此最小值棧里面會有很多重復(fù)元素.因此一個(gè)簡單的優(yōu)化就是：在新值當(dāng)且僅當(dāng)<=原最小值時(shí)郎任，才pushIntoMin秧耗，注意這個(gè)==的條件是不可少的，這是為了防止在pop的時(shí)候錯(cuò)誤的pop最小值涝滴。pop時(shí), 當(dāng)待pop值==最小值時(shí)绣版，popMinStack, 其他時(shí)候不對最小值棧進(jìn)行pop胶台。
下面說一種具有常數(shù)空間復(fù)雜度的方法:
在這個(gè)方法里,只需要額外開一個(gè)用于存放當(dāng)前最小值的變量min即可.因此下面提到的push和pop操作都是對于題目中要求的棧來操作的,當(dāng)然,這也是這個(gè)算法里唯一的棧.
設(shè)push的參數(shù)為v_push,pop的返回值為v_pop.
先說下整體思路:因?yàn)闂Ｖ兴性氐闹刀疾粫∮诋?dāng)其為棧頂元素時(shí)min函數(shù)的值,所以在棧中其實(shí)只需要保存某元素比相應(yīng)最小值大出來的值就可以了.而對于最小值更新的位置,棧元素肯定為0,因此可以利用這個(gè)位置來保存更多的信息,在這里是更新后前兩個(gè)最小值的差值,而這個(gè)值肯定是非正的.
根據(jù)上面的思路,push函數(shù)按照如下策略進(jìn)行:
首先push (v_push-min),如果v_push < min,更新min為v_push.
相應(yīng)的,pop函數(shù)按照如下策略進(jìn)行(稱棧頂元素為top):
如果top >= 0, v_pop = min+top, 如果top < 0, v_pop = min,然后更新min為min-top.
顯然,對于min函數(shù)來說,只需要返回min空間的內(nèi)容即可.
與張霄學(xué)長交流后,學(xué)長也講了一個(gè)類似的方法:
push時(shí)候 如果 v_push >= min, v_push 直接入棧歼疮， 如果 v_push < min, 那么入棧的是 2 * v_push - min, 然后 min = v_push. 出棧時(shí)， 如果棧頂?shù)膖op >= min 直接出诈唬，如果 top < min 則出現(xiàn)異常韩脏，將min作為pop的返回值，另外需要還原前一個(gè)最小值铸磅，方法是 min = 2 * min - top
其實(shí)這兩種方法在思路上是完全一樣的,只是學(xué)長提供的方法里,棧中所有元素都比我的方法里大v_push.不過,這種變化直接帶來的好處是,在不更新最小值的情況下,壓棧值和出棧值都不需要額外的計(jì)算,在高級語言層面上,一次加減法運(yùn)算比單純的賦值至少多了一次訪存操作和一次alu的運(yùn)算,這樣估計(jì)來我的方法耗時(shí)會是學(xué)長方法的2倍左右,雖然時(shí)間復(fù)雜度都是一樣的.
