更詳細(xì)的講解和代碼調(diào)試演示過程，請(qǐng)參看視頻
如何進(jìn)入google,算法面試技能全面提升指南
有一道堆棧相關(guān)算法題，我被面試過兩次以上，看似其在算法面試中出現(xiàn)的概率很高，由此值得我們好好分析下。題目是這樣的：
對(duì)于堆棧的常用操作有, pop 彈出堆棧頂部的元素；push 向堆棧壓入一個(gè)元素；peek 獲得堆棧頂部的元素值，但不彈出堆?！，F(xiàn)在要去你增加一個(gè)操作max， 它的作用是返回堆棧當(dāng)前所有元素中值最大的那個(gè)，例如堆棧當(dāng)前元素有：
stack: 5，4，2，3
那么max() 返回的值就是5. 假設(shè)向堆棧繼續(xù)推入元素后，情況如下：
stack: 5, 4, 2, 3, 6, 1, 10, 8
那么調(diào)用max() 得到的元素為10.
假設(shè)我們現(xiàn)在我們采取pop操作，彈出頂部?jī)蓚€(gè)元素，那么堆棧情況如下：
stack: 5, 4, 2, 3, 6, 1
顯然此時(shí)max 操作返回的元素是6。
請(qǐng)給出一個(gè)時(shí)間復(fù)雜度為O(1)的算法，實(shí)現(xiàn)max操作。
這道題一個(gè)麻煩處在于，如果堆棧僅僅是壓入元素，那么返回最大值是很容易的，只要把當(dāng)前壓入元素的最大值記下來就可以了。問題在于，堆棧還有彈出操作，當(dāng)彈出后，堆棧當(dāng)前的最大元素可能就會(huì)不斷的發(fā)生變化。如果是壓入操作和彈出操作交替進(jìn)行的話，那么情況就更復(fù)雜了。
解決這個(gè)問題的算法如下：
1， 每次壓入元素是，用一個(gè)變量maxVal, 記錄堆棧當(dāng)前元素的最大值。
2， 創(chuàng)建一個(gè)新堆棧maxStack，當(dāng)壓入元素的值大于當(dāng)前元素的最大值時(shí)，把該元素壓入maxStack.
3, 彈出一個(gè)元素時(shí)，如果彈出的元素是當(dāng)前最大值，那么把maxStack頂部的元素也彈出，然后把maxValue設(shè)置成maxStack的頂部元素。
4，執(zhí)行max()操作時(shí)，可以直接返回maxValue, 或是maxStack堆棧的頂部元素。
不難看出，上述操作使得元素壓入時(shí)，maxValue 與 maxStack頂部元素保持一致，當(dāng)元素彈出時(shí)，如果彈出的是當(dāng)前最大值，那么步驟3把maxValue的值設(shè)置成maxStack的頂部元素，因此，無論是壓入還是彈出操作，maxValue與maxStack的始終保持一致。
同時(shí)，當(dāng)只有壓入元素大于當(dāng)前堆棧元素的最大值時(shí)，新元素才會(huì)壓入maxStack,這就保證了maxStack堆棧頂部的元素就是當(dāng)前堆棧中所有元素最大的一個(gè)。
上面算法，執(zhí)行max()操作時(shí)，只需要把maxStack頂部元素彈出或直接返回maxValue,因此時(shí)間復(fù)雜度是O(1), 在特殊情況下，例如所有元素是升序壓入堆棧的，比如壓入的元素為：1，2， 3， 4.那么這些元素除了壓入正常堆棧外，還得全部壓入maxStack, 因此算法的空間復(fù)雜度是O(N).
我們看看具體代碼的實(shí)現(xiàn)：
import java.util.Stack;
public class MaxStack {
private Stack<Integer> stack = new Stack<Integer>();
private int maxVal = Integer.MIN_VALUE;
private Stack<Integer> maxStack = new Stack<Integer>();
public void push(int val) {
if (val >= maxVal) {
maxVal = val;
maxStack.push(maxVal);
}
stack.push(val);
}
public int peek() {
return stack.peek();
}
public int pop() {
if (stack.peek() == maxVal) {
maxStack.pop();
}
maxVal = maxStack.peek();
return stack.pop();
}
public int max() {
return maxStack.peek();
}
}
代碼實(shí)現(xiàn)簡(jiǎn)單，基本上根據(jù)算法步驟來實(shí)現(xiàn)，我們?cè)倏纯粗魅肟谔幍拇a：
public class StackAndQuque {
public static void main(String[] args) {
MaxStack ms = new MaxStack();
ms.push(5);
ms.push(4);
ms.push(2);
ms.push(3);
System.out.println("Max Val in stack is : " + ms.max());
ms.push(6);
ms.push(1);
ms.push(10);
ms.push(8);
System.out.println("Max Val in stack is : " + ms.max());
ms.pop();
ms.pop();
System.out.println("Max Val in stack is : " + ms.max());
ms.push(7);
System.out.println("Max Val in stack is : " + ms.max());
}
}
運(yùn)行結(jié)果如下：
Max Val in stack is : 5
Max Val in stack is : 10
Max Val in stack is : 6
Max Val in stack is : 7
稍微檢測(cè)下便可以發(fā)現(xiàn)，代碼給出的結(jié)果是正確的，更多更詳實(shí)的講解和調(diào)試演示過程，請(qǐng)大家參考視頻。
更多技術(shù)信息，包括操作系統(tǒng)，編譯器，面試算法，機(jī)器學(xué)習(xí)，人工智能，請(qǐng)關(guān)照我的公眾號(hào)：
