目錄
棧的入門題目-最小棧
代碼演示
視頻鏈接
算法講解015【入門】棧的入門題目-最小棧
Leecode155
棧的入門題目-最小棧
實現一個getmin方法（高效方法，即不用遍歷），希望能實現O（1）
做法：準備兩個棧
data和min棧
當我壓入3時，我同步壓入。
如果再加入個5，data棧壓入5。讓最小棧的棧頂和要壓入的數比較。3<5，所以min棧再壓入5。
比如再壓入2，2現在是最小的，所以左右同時壓入2。
比如再壓入7，2目前還是最小的，所以左邊壓入7，右邊壓入2。
總結：就這三條邏輯
1）當前壓的數字<=min棧的頂，當前數字壓入min棧
2）當前壓得數字>min棧的頂，min原來的數壓入min棧
3）min棧為空，data為空，當前要壓的數字壓入min棧
為什么要這么做？
保證一一對應。即永遠右邊的棧頂是棧里元素的最小值。
要彈出的時候，data棧和min棧同步彈出就行
代碼演示
import java.util.Stack;
public class MinStack1 {//data棧：用于存放所有實際的數字public Stack<Integer>data;//min棧：輔助棧，其棧頂永遠是當前data棧中的最小值public Stack<Integer>min;//構造方法：public MinStack1(){//初始化兩個棧data = new Stack<Integer>();min = new Stack<Integer>();}/*** 將一個元素推入棧中*/public void push(int val){//第一步：無論如何，新元素val總是要被推入data棧data.push(val);//第二步：根據規則決定往min棧中推入什么//條件一：min棧為空？（即這是第一個元素，它當然是最小值）//條件二：val<=min.peek()? 如果是的話，那么目前val最小，val壓入到min棧中。//條件一條件二都是將val直接壓入min棧中if(min.isEmpty()||val<=min.peek()){min.push(val);}else{//如果是條件三：即min.peek比val要小，那么再把它壓一遍min.push(min.peek());}}/*** 從棧中彈出一個元素*/public void pop(){//data棧和min棧是嚴格同步的，所以data棧彈出時min棧也應該彈出，以維持同步data.pop();min.pop();}/*** 查看棧頂元素*/public int top(){//棧頂元素就是data棧的棧頂return data.peek();}/*** 獲取棧的最小元素*/public int getMin() {//即min的peekreturn min.peek();}
}但這種方法（即用java自帶的stack類效率低），所以我們選擇用數組來親手搭建一個棧，這樣效率高。
public class MinStack2 {//假設這個棧最多裝8001個元素public final int MAXN = 8001;//用兩個整型數組來代替stack類public int[]data;//對應之前的data棧public int[]min;//對應之前的min棧//變量size：即表示當前元素的數量，也指向下一個要插入的位置int size;//構造方法public MinStack2(){//創建兩個剛好能容納MAXN個整數的數組//相當于建好了兩怕空的儲物柜data = new int[MAXN];min = new int[MAXN ];//初始時一個元素都沒有所以size是0size = 0;}/*** 將一個元素推入我們用數組模擬的棧中*/public void push(int val){//data[size] = val//把新元素val放入data數組的第size個位置//如果size是0，就放在data[0]；如果size是1，就放在data[1]data[size] = val;//data棧壓入之后，我們來想一想min棧怎么辦（和上一題一樣）if(size == 0||val<=min[size-1]){min[size] = val;}else{//否則，最小值不變//復制上一個位置的最小值到當前位置，以保持和data數組的同步min[size] = min[size-1];}//最重要的一步：把size加1，讓指針指向下一個空位//并且表示元素總數增加一個size++;}/*** 從我們用數組模擬的棧中彈出一個元素*/public void pop(){//我們不需要真的去清除數組里的data[size-1]//只需要把size減1，就等于我們邏輯上拋棄了最后一個元素//下次push時，那個位置的值會被自然地覆蓋掉size--;}/*** 查看棧頂元素*/public int top(){//因為size指向地是下一個空位，所以棧真正地頂部元素位于它地前一個位置// 即size-1return data[size-1];}/*** 獲取棧中的最小元素*/public int getMin(){//同理，最小元素即min數組的棧頂位置，也就是size-1return min[size-1];}
}
)
)
