0155. Min Stack
https://leetcode.com/problems/min-stack
Description
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.
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:
-231 <= val <= 231 - 1
Methods
pop
,top
andgetMin
operations will always be called on non-empty stacks.At most
3 * 104
calls will be made topush
,pop
,top
, andgetMin
.
ac1: two stack
class MinStack {
private Stack<Integer> stack;
private Stack<Integer> stack2;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack<>();
stack2 = new Stack<>();
}
public void push(int x) {
stack.push(x);
if (stack2.isEmpty() || x <= stack2.peek()) {
stack2.push(x);
}
}
public void pop() {
int tmp = stack.pop();
if (tmp == stack2.peek()) {
stack2.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return stack2.peek();
}
}
ac2: one stack
Key: in the stack, add some roadmark to indicate min from now on.ß
class MinStack {
private Stack<Integer> stack;
private int min;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack<>();
min = Integer.MAX_VALUE;
}
public void push(int x) {
if (x <= min) {
stack.push(min);
min = x;
}
stack.push(x);
}
public void pop() {
int tmp = stack.pop();
if (tmp == min) {
min = stack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return min;
}
}
Last updated
Was this helpful?