文章目錄

• 題目描述
• 思路 & 代碼
• • • 更新版

題目描述

• 用空間換時間的經典例子，唯一要解決的地方就是 getMin() 如何實現常數檢索
• （貌似也是面試常考題）
  

思路 & 代碼

• 既然想快，那就要付出空間的代價
• 用什么空間可以實現？數組好找，但是不好擴展；鏈表好擴，但是不好找；同樣是順序結構，不可能用隊列，那就用自己吧！來一個輔助棧
• 輔助棧：記錄主棧每個元素為棧頂時，對應的最大值。

class MinStack {private Stack<Integer> stack;private Stack<Integer> helper;// 思路，維護一個最小棧helper，對應當前子棧的最小值/** initialize your data structure here. */public MinStack() {stack = new Stack<>();helper = new Stack<>();}public void push(int val) {stack.push(val);if(helper.empty()){helper.push(val);}else{helper.push(val > helper.peek() ? helper.peek() : val);}}public void pop() {stack.pop();helper.pop();}public int top() {return stack.peek();}public int getMin() {return helper.peek();} }/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(val);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/

更新版

• 換成 ArrayDeque，效率更高了

class MinStack {Deque<Integer> stack;Deque<Integer> minStack;/** initialize your data structure here. */public MinStack() {stack = new ArrayDeque<>();minStack = new ArrayDeque<>();}public void push(int val) {stack.push(val);int min = minStack.isEmpty() ? val : minStack.peek();val = val < min ? val : min;minStack.push(val);}public void pop() {stack.pop();minStack.pop();}public int top() {return stack.peek();}public int getMin() {return minStack.peek();} }

總結

以上是生活随笔為你收集整理的【LeetCode笔记】155. 最小栈（Java、栈）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。