作者 | channingbreeze
小史是一個應屆生，雖然學的是電子專業，但是自己業餘時間看了很多互聯網與編程方面的書，一心想進BAT。
今天他又去BAT中的一家面試了。簡單的自我介紹後，面試官給了小史一個問題。
面試現場
題目：我現在需要實現一個棧，這個棧除了可以進行普通的push、pop操作以外，還可以進行getMin的操作，getMin方法被調用後，會返回當前棧的最小值，你會怎麼做呢？你可以假設棧裡面存的都是int整數。
小史熟練地把代碼寫了出來。
import java.util.ArrayList;
import java.util.List;
/**
* @author xiaoshi on 2018/9/1.
*/
public class MinStack {
private List<integer> data = new ArrayList<integer>();
private List<integer> mins = new ArrayList<integer>();
public void push(int num) {
data.add(num);
if(mins.size() == 0) {
// 初始化mins
mins.add(num);
} else {
// 輔助棧mins每次push當時最小值
int min = getMin();
if (num >= min) {
mins.add(min);
} else {
mins.add(num);
}
}
}
public int pop() {
// 棧空，異常，返回-1
if(data.size() == 0) {
return -1;
}
// pop時兩棧同步pop
mins.remove(mins.size() - 1);
return data.remove(data.size() - 1);
}
public int getMin() {
// 棧空，異常，返回-1
if(mins.size() == 0) {
return -1;
}
// 返回mins棧頂元素
return mins.get(mins.size() - 1);
}
}
/<integer>/<integer>/<integer>/<integer>
請教大神
小史回到學校，把面試的情況，和計算機學院的呂老師說了一下。
異常情況處理
呂老師：面試官已經提出了，你的異常處理有點問題，當棧內為空的時候，你返回-1，但是如果用戶push過-1，那麼你返回-1的時候，是用戶push進來的值，還是棧為空，就不得而知了。
小史咬咬牙：那就再定義一個類，裡面包括一個int的data、和一個boolean的isSuccess，正常情況下isSuccess是true，棧為空的話，isSuccess是false。這樣就能區分開了吧？
小史突然一拍大腿：對哦，我可以用一個包裝類Integer來定義返回值，如果是空，就代表棧為空就行了。它和int的區別就是它多了一個null，正好用來返回異常情況。
呂老師：嗯，越來越好，但是還是有點問題。你並沒有站在使用者的角度，考慮問題。使用你這個棧的人，在pop的時候，他並不知道可能返回null，如果他不做判斷，後面的代碼，就可能拋出空指針了。
呂老師發來一個表情。
呂老師：沒錯，最關鍵的是，你顯式拋出異常，如果使用者不捕獲，那麼編譯就會報錯，這樣就把錯誤，暴露在編譯階段，並且不需要和任何人，商量所謂的特殊返回值了。
算法優化
呂老師一眼看穿了小史的心思。
小史想了想：明白了，我可以在push的時候判斷一下，如果比最小值還大，就不加入輔助棧。pop的時候，如果不是最小值，輔助棧就不出棧。這樣一來，輔助棧就不會有大量重複元素了。
小史：push的時候進行判斷，如果數值比當前最小值大，就不動mins棧了，這樣mins棧中，不會保存大量冗餘的最小值。pop的時候同樣進行判斷，只有pop出的數，就是當前最小值的時候，才讓mins出棧。
小史：如果push一個和最小值相等的元素，還是要入mins棧。不然當這個最小值pop出去的時候。data中還會有一個最小值元素，而mins中卻已經沒有最小值元素了。
小史：mins棧中改存最小值在data數組中的索引。這樣一來，當push了與最小值相同元素的時候，就不需要動mins棧了。而pop的時候，pop出的元素的索引，如果不是mins棧頂元素，mins也不出棧。同時，獲取最小值的時候，需要拿到mins棧頂元素作為索引，再去data數組中，找到相應的數，作為最小值。
理解了算法之後，小史的代碼，寫起來也是非常快，不一會兒就寫好了：
import java.util.ArrayList;
import java.util.List;
/**
* @author xiaoshi on 2018/9/1.
*/
public class MinStack {
private List<integer> data = new ArrayList<integer>();
private List<integer> mins = new ArrayList<integer>();
public void push(int num) throws Exception {
data.add(num);
if(mins.size() == 0) {
// 初始化mins
mins.add(0);
} else {
// 輔助棧mins push最小值的索引
int min = getMin();
if (num < min) {
mins.add(data.size() - 1);
}
}
}
public int pop() throws Exception {
// 棧空，拋出異常
if(data.size() == 0) {
throw new Exception("棧為空");
}
// pop時先獲取索引
int popIndex = data.size() - 1;
// 獲取mins棧頂元素，它是最小值索引
int minIndex = mins.get(mins.size() - 1);
// 如果pop出去的索引就是最小值索引，mins才出棧
if(popIndex == minIndex) {
mins.remove(mins.size() - 1);
}
return data.remove(data.size() - 1);
}
public int getMin() throws Exception {
// 棧空，拋出異常
if(data.size() == 0) {
throw new Exception("棧為空");
}
// 獲取mins棧頂元素，它是最小值索引
int minIndex = mins.get(mins.size() - 1);
return data.get(minIndex);
}
}
/<integer>/<integer>/<integer>/<integer>
小史的疑惑
吃飯的時候，小史提出了心中埋藏已久的疑惑。
呂老師：數據結構和算法的設計，是一個程序員的內功，工作時雖然用不到這麼細，但是你在學習其他知識的底層原理的時候，到處都是數據結構和算法。
作者簡介：channingbreeze，國內某互聯網公司全棧開發。
“徵稿啦”
CSDN 公眾號秉持著「與千萬技術人共成長」理念，不僅以「極客頭條」、「暢言」欄目在第一時間以技術人的獨特視角描述技術人關心的行業焦點事件，更有「技術頭條」專欄，深度解讀行業內的熱門技術與場景應用，讓所有的開發者緊跟技術潮流，保持警醒的技術嗅覺，對行業趨勢、技術有更為全面的認知。
如果你有優質的文章，或是行業熱點事件、技術趨勢的真知灼見，或是深度的應用實踐、場景方案等的新見解，歡迎聯繫 CSDN 投稿，聯繫方式：微信（guorui_1118，請備註投稿+姓名+公司職位），郵箱（guorui@csdn.net）。