[LeetCode] #155 Min Stack (Easy)
LeetCode 第 155 題 Min Stack，難度 Easy
用 Python3 解 LeetCode 系列，Min Stack，屬於 Easy
原始題目
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack()initializes the stack object.void push(int val)pushes the element val onto the stack.void pop()removes the element on the top of the stack.int top()gets the top element of the stack.int getMin()retrieves the minimum element in the stack.
Example 1:
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2
題目分析
設計具有 push, pop, top 操作，並能在常數時間 O(n) 內查詢到最小元素的堆疊
解題過程
- 建立一個 list
min_stack紀錄堆疊最小值 - 建立
stacklist 作為堆疊紀錄 - push：把值放進堆疊後面，如果該值小於等於 min_stack 堆疊的最後一筆資料，則一併加入 min_stack 堆疊
- pop：從 stack 移除最上面一筆值，如果該值等於 min_stack 最後一筆，一併從堆疊移除
- top：取得堆疊最上面一個元素
stack[-1] - getMin：取得最小值，也就是 min_stack 的最後一個元素
min_stack[-1]
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val: int) -> None:
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self) -> None:
if self.stack.pop() == self.min_stack[-1]:
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
結果
