LeetCode155:最小棧，最簡單的中等難度題，時間擊敗100%，記憶體也低於官方
2023-09-11 09:00:59
歡迎存取我的GitHub
這裡分類和彙總了欣宸的全部原創(含配套原始碼)：https://github.com/zq2599/blog_demos
本篇概覽
- 最近運氣不錯，在LeetCode上白撿一道送分題，官方設定的難度是中等，然而此題難度放在簡單的題庫中都是墊底的存在，對於刷題數太少的欣宸而言，這簡直就是力扣的饋贈，建議大家也不要錯過，花上幾分鐘將其拿下
- 不嘮嗑了，下面咱們一起來刷之
- 為了提起您的興趣，這裡提前劇透一下：
- 用最簡單的資料結構-陣列，來儲存資料，程式碼整體非常簡單，適合新手閱讀
- 執行用時執行用時3毫秒, 在所有 Java 提交中擊敗了100%的使用者（包括官方），有下圖為證
題目說明
- 設計一個支援 push ，pop ，top 操作，並能在常數時間內檢索到最小元素的棧。
- 實現 MinStack 類:
- MinStack() 初始化堆疊物件。
- void push(int val) 將元素val推入堆疊。
- void pop() 刪除堆疊頂部的元素。
- int top() 獲取堆疊頂部的元素。
- int getMin() 獲取堆疊中的最小元素。
- 範例1
輸入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
輸出：
[null,null,null,null,-3,null,0,-2]
解釋：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
- 提示
- -231 <= val <= 231 - 1
- pop、top 和 getMin 操作總是在 非空棧 上呼叫
- push, pop, top, and getMin最多被呼叫 30000 次
官方解法
- 先來看官方解法，簡單的說，就是用JDK已有的棧物件Deque來完成push、pop、top等操作，如下所示
class MinStack {
Deque<Integer> xStack;
Deque<Integer> minStack;
public MinStack() {
xStack = new LinkedList<Integer>();
minStack = new LinkedList<Integer>();
minStack.push(Integer.MAX_VALUE);
}
public void push(int x) {
xStack.push(x);
minStack.push(Math.min(minStack.peek(), x));
}
public void pop() {
xStack.pop();
minStack.pop();
}
public int top() {
return xStack.peek();
}
public int getMin() {
return minStack.peek();
}
}
- 讀完這段程式碼我就茫然了：我來LeetCode刷題是為了什麼？為了學習Deque類的API使用方法嗎？
- 不，我是來學習和提升自己的演演算法能力的，這種API呼叫並不是我心目中的答案，官方找不到，我就自己動手
- 畢竟，實現個棧能有多大難度？
- 為了弄清楚自己和官方的差距，我先將上述官方原始碼提交一次，看看成績如何，如下圖，官方在使用Deque類的情況下，執行用時擊敗93%，記憶體消耗擊敗57%
- 接下來該我了，自己實現棧
題目分析
- 前面廢話太多，這裡精簡一下，說說我理解的此題的重點
- 資料結構：怎麼存資料，才能保證高效的讀寫速度？
- 最小值問題：本題不僅要有基本的棧功能，還要時刻能返回棧內的最小值
- 記憶體怎麼優化？
- 耗時怎麼優化？
- 接下來針對上述問題，逐個考慮
問題一：資料結構設計
- 最高效的存取，一般是陣列和連結串列，在java中，原始型別的陣列更簡單，而連結串列就要用到物件了，相對更復雜，所以，陣列是首選，至於用陣列實現後進先出的棧，那也簡單嘛，用個int型變數做指標即可
- 如下圖，例如固定長度10的陣列，裡面存了兩個有效資料，int型變數pointer等於1即可，表示陣列的位置1儲存著最後一個有效資料，後面再加入新的資料時，放在pointer+1的位置即可
最小值問題
- 題目要求中規定了getMin方法要返回當前棧內的最小值，所以我們要搞清楚什麼時候最小值會發生變化：
- 棧內增加元素時，可能新增的元素比棧內元素都小
- 棧內彈出元素時，可能彈出的元素是最小的那個
- 對於增加元素時的處理最簡單：準備個成員變數min，每次增加元素時，都比較增加的元素和當前min誰最小，最小的更新到min中
- 但是，彈出時呢？最小值被彈出去了，那麼原本次小的就成了最小的，但是次小的咱們沒存啊，這時候有兩種選擇：
- 首先，參考官方原始碼，再準備一個陣列，每次增加時，就把最小值放進來
- 其次，每次彈出時，再重新算一遍最小值，O(n)的耗時，感覺還好...
- 斟酌再三，方案一會導致記憶體翻倍，所以還是優先考慮方案二吧，也就是每次彈出時重新計算一遍最小值
記憶體怎麼優化？
- 接下來要考慮如何少使用記憶體
- 首先要搞清楚的是：準備多大的陣列才能滿足題目要求，官方說明如下圖，注意紅色箭頭，如果呼叫三萬次push，那就說明會存三萬個int數位，所以陣列長度如果低於三萬，提交後就可能報錯，達不到官方要求
- 所以，陣列的長度固定是三萬嗎？
- 當然不需要，提交程式碼後，LeetCode會執行多個用例，不可能每個用例都push三萬次的，所以固定三萬的長度，看似保險，實則浪費
- 所以，優化思路可以借鑑HashMap的原始碼：存不下的時候，就擴容，也就是準備一個新陣列，把老陣列的資料複製進去，至於擴多少？邏輯不必太複雜，翻倍即可
耗時怎麼優化
- 還有最後一個問題要考慮：時間還能優化嗎？
- 要想優化時間，首先咱們要知道哪裡會耗時，回顧前面的設計，最耗時的地方應該是彈出元素的時候，這時候要重新計算最小值，時間複雜度是O(n)，每次彈出都要執行，有沒有可能優化一下呢？
- 考慮下圖這種情況，棧內資料是1、2、3，其中1在棧頂，那麼彈出1之後，自然要在2和3中尋找最小值作為棧的最小值了，這是必要操作，不能優化
- 但是下圖這種情況呢？3在棧頂，彈出去之後，1還是最小值，此時就沒有必要重新比較一遍了
- 好了，分析和設計都完成了，也該寫程式碼驗證效果了，我有種預感，自己設計的棧，比LeetCode官方的更快，也更省記憶體，希望不要被現實打臉...
編碼
- 完整程式碼如下，有了前面的詳細分析，相信您可以輕鬆看懂，注意我這裡陣列的初始長度是64，您也可以調整成其他值試試
class MinStack {
private int[] array = new int[64];
private int pointer = -1;
private int min = Integer.MAX_VALUE;
public MinStack() {
}
public void push(int val) {
array[++pointer] = val;
min = Math.min(min, val);
// 擴容
if (pointer==(array.length-1)) {
int[] temp = new int[array.length*2];
System.arraycopy(array, 0, temp, 0, array.length);
array = temp;
}
}
public void pop() {
pointer--;
// 這裡可以優化：如果彈出的不是最小值，那就沒必要重算呀！
if (array[pointer+1]==min) {
min = Integer.MAX_VALUE;
for (int i=0;i<=pointer;i++) {
min = Math.min(min, array[i]);
}
}
}
public int top() {
return array[pointer];
}
public int getMin() {
return min;
}
}
- 提交，順利AC，成績如下，用時和記憶體雙雙優於官方，尤其是用時，擊敗百分百！
- 至此，第155題順利完成，自我感覺是有一些收穫的，至少比官方的面向API程式設計收穫更大，更何況成績比官方的還好一些...