155. Min Stack
155. Min Stack
题目
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 elementval
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.
You must implement a solution with O(1)
time complexity for each function.
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
Constraints:
-2^31 <= val <= 2^31 - 1
- Methods
pop
,top
andgetMin
operations will always be called on non-empty stacks. - At most
3 * 10^4
calls will be made topush
,pop
,top
, andgetMin
.
题目大意
设计一个支持 push
,pop
,top
操作,并能在常数时间内检索到最小元素的栈。
解题思路
可以在元素每次入栈时,将当前栈内的最小元素作为数组的第二个参数一起入栈,同时保存当前值和栈内最小值:[val, min]
,这样不管出栈时栈内最小元素如何变化,都可以直接返回 min
。
代码
class MinStack {
constructor() {
this.stack = [];
}
// @param {number} val
// @return {void}
push(val) {
if (this.stack.length === 0) {
this.stack.push([val, val]);
} else {
let min = this.stack[this.stack.length - 1][1];
min = val < min ? val : min;
this.stack.push([val, min]);
}
}
// @return {void}
pop() {
this.stack.pop();
}
// @return {number}
top() {
return this.stack[this.stack.length - 1][0];
}
// @return {number}
getMin() {
return this.stack[this.stack.length - 1][1];
}
}
/**
* Your MinStack object will be instantiated and called as such:
* var obj = new MinStack()
* obj.push(val)
* obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.getMin()
*/
相关题目
- [239. 滑动窗口最大值](https://leetcode.com/problems/sliding-window-maximum)
- [🔒 Max Stack](https://leetcode.com/problems/max-stack)