155. Min Stack
設計一個支持以下操作的棧：push、pop、top 和檢索最小元素，並且操作時間複雜度均為常數時間。
實現 MinStack 類：MinStack() 初始化棧對象。
void push(int val) 將元素 val 推入棧中。
void pop() 移除棧頂元素。
int top() 獲取棧頂元素。
int getMin() 檢索棧中的最小元素。
你必須實現每個函數的時間複雜度為 O(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
Python
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:
val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()
def top(self) -> int:
if self.stack:
return self.stack[-1]
return None
def getMin(self) -> int:
if self.min_stack:
return self.min_stack[-1]
return None
20.57MB, 48ms
C++
#include <stack>
using namespace std;
class MinStack {
public:
MinStack() {
}
void push(int val) {
stack.push(val);
if (minStack.empty() || val <= minStack.top()) {
minStack.push(val);
}
}
void pop() {
if (stack.top() == minStack.top()) {
minStack.pop();
}
stack.pop();
}
int top() {
return stack.top();
}
int getMin() {
return minStack.top();
}
private:
std::stack<int> stack;
std::stack<int> minStack;
};
20.92MB, 12ms
Javascript
var MinStack = function() {
this.stack = [];
this.minStack = [];
};
/**
* @param {number} val
* @return {void}
*/
MinStack.prototype.push = function(val) {
this.stack.push(val);
if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
this.minStack.push(val);
}
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
if (this.stack.pop() === 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.getMin = function() {
return this.minStack[this.minStack.length - 1];
};
58.81MB, 94ms
