Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- getMin() -- Retrieve the minimum element in the stack.
設(shè)計(jì)一個(gè)棧, 支持4種操作: push, pop, top和getMin, 關(guān)鍵是getMin是獲取棧中的最小值.
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.
基本代碼框架:
class MinStack {
/** initialize your data structure here. */
public MinStack() {
}
public void push(int x) {
}
public void pop() {
}
public int top() {
}
public int getMin() {
}
}
在線測(cè)試網(wǎng)站: https://leetcode.com/problems/min-stack/description/
class MinStack {
//存gap, 當(dāng)前棧頂和之前的最小值的差值
Stack<Long> stack = new Stack<>();
long min = Integer.MIN_VALUE;
public void push(int x) {
if (stack.isEmpty()) {
stack.push(0L);//初始值存0
min = x;
} else {
stack.push(x - min);//存gap
if (x < min) {
min = x;
}
}
}
public void pop() {
if (stack.isEmpty()) {
return;
}
long peek = stack.peek();
if (peek > 0) {
stack.pop();
} else {
min -= peek;
stack.pop();
}
}
public int top() {
if (stack.isEmpty()) {
return -1;
}
if (stack.peek() > 0) {
return (int)(min + stack.peek());
} else {
return (int)min;
}
}
public int getMin() {
return (int) min;
}
}
