0155. 最小棧 · ttttt

# 0155. 最小棧 # 題目地址(155. 最小棧) <https://leetcode-cn.com/problems/min-stack/> # 題目描述 ``` <pre class="calibre18">``` 設計一個支持 push ，pop ，top 操作，并能在常數時間內檢索到最小元素的棧。 push(x) —— 將元素 x 推入棧中。 pop() —— 刪除棧頂的元素。 top() —— 獲取棧頂元素。 getMin() —— 檢索棧中的最小元素。示例: 輸入： ["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. 提示： pop、top 和 getMin 操作總是在非空棧上調用。 ``` ``` ## 前置知識 - [棧](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md)## 公司 - amazon - bloomberg - google - snapchat - uber - zenefits ## 兩個棧 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ### 思路我們使用兩個棧： - 一個棧存放全部的元素，push，pop都是正常操作這個正常棧。 - 另一個存放最小棧。每次push，如果比最小棧的棧頂還小，我們就push進最小棧，否則不操作 - 每次pop的時候，我們都判斷其是否和最小棧棧頂元素相同，如果相同，那么我們pop掉最小棧的棧頂元素即可 ### 關鍵點 - 往minstack中 push的判斷條件。應該是stack為空或者x小于等于minstack棧頂元素 ### 代碼 - 語言支持：JS，C++，Java，Python JavaScript Code: ``` <pre class="calibre18">``` /** * initialize your data structure here. */ var MinStack = function() { this.stack = [] this.minStack = [] }; /** * @param {number} x * @return {void} */ MinStack.prototype.push = function(x) { this.stack.push(x) if (this.minStack.length == 0 || x <= this.minStack[this.minStack.length - 1]) { this.minStack.push(x) } }; /** * @return {void} */ MinStack.prototype.pop = function() { const x = this.stack.pop() if (x !== void 0 && x === this.minStack[this.minStack.length - 1]) { this.minStack.pop() } }; /** * @return {number} */ MinStack.prototype.top = function() { return this.stack[this.stack.length - 1] }; /** * @return {number} */ MinStack.prototype.min = function() { return this.minStack[this.minStack.length - 1] }; /** * Your MinStack object will be instantiated and called as such: * var obj = new MinStack() * obj.push(x) * obj.pop() * var param_3 = obj.top() * var param_4 = obj.min() */ ``` ``` C++ Code: ``` <pre class="calibre18">``` class MinStack { stack<int> data; stack<int> helper; public: /** initialize your data structure here. */ MinStack() { } void push(int x) { data.push(x); if(helper.empty() || helper.top() >= x) { helper.push(x); } } void pop() { int top = data.top(); data.pop(); if(top == helper.top()) { helper.pop(); } } int top() { return data.top(); } int getMin() { return helper.top(); } }; /** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(x); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */ ``` ``` Java Code: ``` <pre class="calibre18">``` public class MinStack { // 數據棧 private Stack<Integer> data; // 輔助棧 private Stack<Integer> helper; /** * initialize your data structure here. */ public MinStack() { data = new Stack<>(); helper = new Stack<>(); } public void push(int x) { // 輔助棧在必要的時候才增加 data.add(x); if (helper.isEmpty() || helper.peek() >= x) { helper.add(x); } } public void pop() { // 關鍵 3：data 一定得 pop() if (!data.isEmpty()) { // 注意：聲明成 int 類型，這里完成了自動拆箱，從 Integer 轉成了 int， // 因此下面的比較可以使用 "==" 運算符 int top = data.pop(); if(top == helper.peek()){ helper.pop(); } } } public int top() { if(!data.isEmpty()){ return data.peek(); } } public int getMin() { if(!helper.isEmpty()){ return helper.peek(); } } } ``` ``` Python3 Code: ``` <pre class="calibre18">``` class MinStack: def __init__(self): """ initialize your data structure here. """ self.stack = [] self.minstack = [] def push(self, x: int) -> None: self.stack.append(x) if not self.minstack or x <= self.minstack[-1]: self.minstack.append(x) def pop(self) -> None: tmp = self.stack.pop() if tmp == self.minstack[-1]: self.minstack.pop() def top(self) -> int: return self.stack[-1] def min(self) -> int: return self.minstack[-1] # Your MinStack object will be instantiated and called as such: # obj = MinStack() # obj.push(x) # obj.pop() # param_3 = obj.top() # param_4 = obj.min() ``` ``` **復雜度分析** - 時間復雜度：O(1) - 空間復雜度：O(1) ## 一個棧 ### 思路符合直覺的方法是，每次對棧進行修改操作（push和pop）的時候更新最小值。然后getMin只需要返回我們計算的最小值即可， top也是直接返回棧頂元素即可。這種做法每次修改棧都需要更新最小值，因此時間復雜度是O(n). ![](https://img.kancloud.cn/55/26/5526b3eb9039ee54be1f1a9c4c96c34b_474x340.jpg) 是否有更高效的算法呢？答案是有的。我們每次入棧的時候，保存的不再是真正的數字，而是它與當前最小值的差（當前元素沒有入棧的時候的最小值）。這樣我們pop和top的時候拿到棧頂元素再加上**上一個**最小值即可。另外我們在push和pop的時候去更新min，這樣getMin的時候就簡單了，直接返回min。 > 注意上面加粗的“上一個”，不是“當前的最小值” 經過上面的分析，問題的關鍵轉化為“如何求得上一個最小值”，解決這個的關鍵點在于利用min。 pop或者top的時候： - 如果棧頂元素小于0，說明棧頂是當前最小的元素，它出棧會對min造成影響，我們需要去更新min。上一個最小的是“min - 棧頂元素”,我們需要將上一個最小值更新為當前的最小值 > 因為棧頂元素入棧的時候的通過 `棧頂元素 = 真實值 - 上一個最小的元素` 得到的，而真實值 = min，因此可以得出`上一個最小的元素 = 真實值 -棧頂元素` - 如果棧頂元素大于0，說明它對最小值`沒有影響`，上一個最小值就是上上個最小值。 ![](https://img.kancloud.cn/b5/04/b504c643616bad12a304d29af69d6179_702x721.jpg)![](https://img.kancloud.cn/47/d6/47d677c8caacba569088093b2bab7a11_641x400.jpg) ### 關鍵點 - 最小棧存儲的不應該是真實值，而是真實值和min的差值 - top的時候涉及到對數據的還原，這里千萬注意是**上一個**最小值 ### 代碼 - 語言支持：JS，C++，Java，Python Javascript Code: ``` <pre class="calibre18">``` /* * @lc app=leetcode id=155 lang=javascript * * [155] Min Stack */ /** * initialize your data structure here. */ var MinStack = function() { this.stack = []; this.minV = Number.MAX_VALUE; }; /** * @param {number} x * @return {void} */ MinStack.prototype.push = function(x) { // update 'min' const minV = this.minV; if (x < this.minV) { this.minV = x; } return this.stack.push(x - minV); }; /** * @return {void} */ MinStack.prototype.pop = function() { const item = this.stack.pop(); const minV = this.minV; if (item < 0) { this.minV = minV - item; return minV; } return item + minV; }; /** * @return {number} */ MinStack.prototype.top = function() { const item = this.stack[this.stack.length - 1]; const minV = this.minV; if (item < 0) { return minV; } return item + minV; }; /** * @return {number} */ MinStack.prototype.min = function() { return this.minV; }; /** * Your MinStack object will be instantiated and called as such: * var obj = new MinStack() * obj.push(x) * obj.pop() * var param_3 = obj.top() * var param_4 = obj.min() */ ``` ``` C++ Code: ``` <pre class="calibre18">``` class MinStack { stack<long> data; long min = INT_MAX; public: /** initialize your data structure here. */ MinStack() { } void push(int x) { data.push(x - min); if(x < min) { min = x; } } void pop() { long top = data.top(); data.pop(); // 更新最小值 if(top < 0) { min -= top; } } int top() { long top = data.top(); // 最小值為 min if (top < 0) { return min; } else{ return min+top; } } int getMin() { return min; } }; /** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(x); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */ ``` ``` Java Code: ``` <pre class="calibre18">``` class MinStack { long min; Stack<Long> stack; /** initialize your data structure here. */ public MinStack() { stack = new Stack<>(); } public void push(int x) { if (stack.isEmpty()) { stack.push(0L); min = x; } else { stack.push(x - min); if (x < min) min = x; } } public void pop() { long p = stack.pop(); if (p < 0) { // if (p < 0), the popped value is the min // Recall p is added by this statement: stack.push(x - min); // So, p = x - old_min // old_min = x - p // again, if (p < 0), x is the min so: // old_min = min - p min = min - p; } } public int top() { long p = stack.peek(); if (p < 0) { return (int) min; } else { // p = x - min // x = p + min return (int) (p + min); } } public int getMin() { return (int) min; } } ``` ``` Python Code: ``` <pre class="calibre18">``` class MinStack: def __init__(self): """ initialize your data structure here. """ self.minV = float('inf') self.stack = [] def push(self, x: int) -> None: self.stack.append(x - self.minV) if x < self.minV: self.minV = x def pop(self) -> None: if not self.stack: return tmp = self.stack.pop() if tmp < 0: self.minV -= tmp def top(self) -> int: if not self.stack: return tmp = self.stack[-1] if tmp < 0: return self.minV else: return self.minV + tmp def min(self) -> int: return self.minV # Your MinStack object will be instantiated and called as such: # obj = MinStack() # obj.push(x) # obj.pop() # param_3 = obj.top() # param_4 = obj.min() ``` ``` **復雜度分析** - 時間復雜度：O(1) - 空間復雜度：O(1) 更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經37K star啦。關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)