Min Stack
ID
155
Data Type
Stack
Difficulty
Medium
Tags
Completed Date
May 10, 2024
Preference
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 elementvalonto 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:
Constraints:
231 <= val <= 231 - 1
- Methods
pop,topandgetMinoperations will always be called on non-empty stacks.
- At most
3 * 104calls will be made topush,pop,top, andgetMin.
题解
这个题关键点在
this.min = append(this.min, min) ，这行代码的作用是将当前的最小值 min 添加到 min 列表的末尾。当你调用
this.Push(x) 方法时，它会将 x 添加到 elements 列表的末尾，并更新 min 列表。具体来说，如果 x 小于当前的最小值，那么 x 就会被添加到 min 列表的末尾，否则当前的最小值会被再次添加到 min 列表的末尾。这样做的好处是，无论何时调用 this.GetMin() 方法，它都可以立即返回当前栈顶元素的最小值，而不需要遍历整个 elements 列表。因为要求只要维护最小值列表，this.min 数组用于存储每次入栈操作后的最小值。这样，this.min 的最后一个元素总是当前栈中的最小值。当一个元素被压入栈时，它会与当前的最小值进行比较。如果它比当前的最小值小，那么它就成为新的最小值，并被添加到
this.min 中。否则，当前的最小值会再次被添加到 this.min 中。这样做的好处是，当最小值被弹出栈时，下一个最小值已经在 this.min 的倒数第二个位置了。这就是
this.min = append(this.min, min) 这行代码的巧妙之处。它使得我们可以在常数时间内获取到当前栈中的最小值，而无需遍历整个栈。同时，它也保证了 this.min 数组和 this.elements 数组的长度始终是一致的，这使得我们在弹出元素时可以很方便地同时更新两个数组。