小结:
1、
常数时间内检索到最小元素
2、存储
存储绝对值?相对值
存储差异
3、
java-ide-debug
最小栈 - 力扣(LeetCode)
https://leetcode-cn.com/problems/min-stack/
设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。
- push(x) -- 将元素 x 推入栈中。
- pop() -- 删除栈顶的元素。
- top() -- 获取栈顶元素。
- getMin() -- 检索栈中的最小元素。
示例:
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
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.
package leetcode;
import java.util.Stack;
class MinStack {
int min = Integer.MAX_VALUE;
Stack<Integer> stack = new Stack<Integer>();
public static void main(String[] args) {
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();
minStack.pop();
minStack.top();
minStack.getMin();
}
public void push(int x) {
// only push the old minimum value when the current
// minimum value changes after pushing the new value x
if (x <= min) {
stack.push(min);
min = x;
}
stack.push(x);
}
public void pop() {
// if pop operation could result in the changing of the current minimum value,
// pop twice and change the current minimum value to the last minimum value.
if (stack.pop() == min) min = stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return min;
}
}
(3) Clean 6ms Java solution - LeetCode Discuss
https://leetcode.com/problems/min-stack/discuss/49010/Clean-6ms-Java-solution
不借助java stack
package leetcode;
class MinStack {
private Node head;
public void push(int x) {
if (head == null)
head = new Node(x, x);
else
head = new Node(x, Math.min(x, head.min), head);
}
public void pop() {
head = head.next;
}
public int top() {
return head.val;
}
public int getMin() {
return head.min;
}
private class Node {
int val;
int min;
Node next;
private Node(int val, int min) {
this(val, min, null);
}
private Node(int val, int min, Node next) {
this.val = val;
this.min = min;
this.next = next;
}
}
}
(3) Share my Java solution with ONLY ONE stack - LeetCode Discuss
https://leetcode.com/problems/min-stack/discuss/49031/Share-my-Java-solution-with-ONLY-ONE-stack
The question is ask to construct One stack. So I am using one stack.
The idea is to store the gap between the min value and the current value;
The problem for my solution is the cast. I have no idea to avoid the cast. Since the possible gap between the current value and the min value could be Integer.MAX_VALUE-Integer.MIN_VALUE;
public class MinStack {
long min;
Stack<Long> stack;
public MinStack(){
stack=new Stack<>();
}
public void push(int x) {
if (stack.isEmpty()){
stack.push(0L);
min=x;
}else{
stack.push(x-min);//Could be negative if min value needs to change
if (x<min) min=x;
}
}
public void pop() {
if (stack.isEmpty()) return;
long pop=stack.pop();
if (pop<0) min=min-pop;//If negative, increase the min value
}
public int top() {
long top=stack.peek();
if (top>0){
return (int)(top+min);
}else{
return (int)(min);
}
}
public int getMin() {
return (int)min;
}
}
It's brilliant to store only the difference!! But regarding pop, doesn't it return nothing? Isn't it defined as public void pop(){}
//long pop=stack.pop();