155. Min Stack

🟠   🔖  栈 设计  🔗 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. 滑动窗口最大值
• 🔒 Max Stack

- [239. 滑动窗口最大值](https://leetcode.com/problems/sliding-window-maximum)
- [🔒 Max Stack](https://leetcode.com/problems/max-stack)