Min Stack
Design a stack of integers that, besides the usual operations, can report the smallest value currently in the stack in constant time.
Implement the class MinStack:
new MinStack()creates an empty stack.push(val)putsvalon top of the stack.pop()removes the element on top.top()returns the element on top without removing it.getMin()returns the smallest element in the stack.
push and pop don't return anything. Every method must run in O(1) time, and pop, top and getMin are only called when the stack is not empty.
Each test is a sequence of calls. The first call creates the object. Calls that return nothing are shown as null in the expected output, and their return value isn't checked.
Constraints
-2^31 <= val <= 2^31 - 1- At most
3 * 10^4calls in total.
Examples
Example 1
Input: ["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[3],[5],[2],[],[],[],[]]
Output: [null,null,null,null,2,null,5,3]After pushing 3, 5 and 2 the minimum is 2. Popping 2 leaves 3 and 5: the top is 5 and the minimum goes back to 3.
Example 2
Input: ["MinStack","push","push","push","getMin","pop","getMin","pop","getMin"]
[[],[2],[1],[1],[],[],[],[],[]]
Output: [null,null,null,null,1,null,1,null,2]There are two copies of 1. Popping one copy must leave the minimum at 1; only after both are gone does it go back to 2.
Example 3
Input: ["MinStack","push","top","getMin"]
[[],[5],[],[]]
Output: [null,null,5,5]With a single value, it is both the top and the minimum.
Each test creates the class with the first operation, then calls the methods in order. Output lists what each call returns; null marks the constructor and methods that return nothing, and their return values aren't checked.
JavaScript you'll use: Classes for data structures Stacks, queues and deques
class MinStack {
constructor() {
}
/**
* @param {number} val
* @return {void}
*/
push(val) {
}
/** Removes the top element. @return {void} */
pop() {
}
/** @return {number} the top element */
top() {
}
/** @return {number} the smallest element in the stack */
getMin() {
}
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.