155. 最小栈

🟠   🔖  栈 设计  🔗 力扣 LeetCode

题目

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.

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 and getMin operations will always be called on non-empty stacks.
• At most 3 * 10^4 calls will be made to push, pop, top, and getMin.

题目大意

设计一个支持 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	滑动窗口最大值	[✓]	队列 数组 滑动窗口 2+
716	最大栈 🔒		栈 设计 链表 2+