【LeetCode每日打卡】155. 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.
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:
Methods pop, top and getMin operations will always be called on non-empty stacks.
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/min-stack 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
两个栈一个普通栈，一个用来存储最小值。
class MinStack {
private Stack<Integer> minStack;
private Stack<Integer> stack;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack<>();
minStack = new Stack();
}
public void push(int x) {
stack.push(x);
if(!minStack.isEmpty()){
int top = minStack.peek();
if(x<top){
minStack.push(x);
}else{
minStack.push(top);
}
}else{
minStack.push(x);
}
}
public void pop() {
minStack.pop();
stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/开始优化对最小栈进行优化
注意判断 两个栈时不能用 == 因为是 Integer 要用equals
if(minStack.peek().equals(stack.peek())){
改动 push方法
if(x<=top){ minStack.push(x); }
pop方法
if(minStack.peek().equals(stack.peek())){ minStack.pop(); }
class MinStack {
private Stack<Integer> minStack;
private Stack<Integer> stack;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack<>();
minStack = new Stack();
}
public void push(int x) {
stack.push(x);
if(!minStack.isEmpty()){
int top = minStack.peek();
if(x<=top){
minStack.push(x);
}
}else{
minStack.push(x);
}
}
public void pop() {
if(minStack.peek().equals(stack.peek())){
minStack.pop();
}
stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/方法三两个栈合成一个栈
遇到需要更新 最小值的时候 就把上一个最小值 也压进去，当最小值需要更新时，再弹出来的就是上一次最小值
class MinStack {
private int minStack = Integer.MAX_VALUE;
private Stack<Integer> stack;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack<>();
}
public void push(int x) {
if(x <= minStack){
stack.push(minStack);
minStack = x;
}
stack.push(x);
}
public void pop() {
if(stack.pop() == minStack) {
minStack=stack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack;
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/方法四
差值存储
想不到 评论区各种大神 出没
每次存储 当前值和最小值的差值，如果当前值和最小值的差值 是负数了，说明需要 更换最小值了。
public class MinStack {
long min;
Stack<Long> stack;
public MinStack(){
stack=new Stack<>();
}
public void push(int x) {
if (stack.isEmpty()) {
min = x;
stack.push(x - min);
} else {
stack.push(x - min);
if (x < min){
min = x; // 更新最小值
}
}
}
public void pop() {
if (stack.isEmpty())
return;
long pop = stack.pop();
//弹出的是负值，要更新 min
if (pop < 0) {
min = min - pop;
}
}
public int top() {
long top = stack.peek();
//负数的话，出栈的值保存在 min 中
if (top < 0) {
return (int) (min);
//出栈元素加上最小值即可
} else {
return (int) (top + min);
}
}
public int getMin() {
return (int) min;
}
}
作者：windliang
链接：https://leetcode-cn.com/problems/min-stack/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-38/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。方法五
存成一个节点 包含两个信息 其实和两个栈的方法一思想一样，代码实现更加 简单不会出错
class MinStack {
class Node{
int value;
int min;
Node next;
Node(int x, int min){
this.value=x;
this.min=min;
next = null;
}
}
Node head;
//每次加入的节点放到头部
public void push(int x) {
if(null==head){
head = new Node(x,x);
}else{
//当前值和之前头结点的最小值较小的做为当前的 min
Node n = new Node(x, Math.min(x,head.min));
n.next=head;
head=n;
}
}
public void pop() {
if(head!=null)
head =head.next;
}
public int top() {
if(head!=null)
return head.value;
return -1;
}
public int getMin() {
if(null!=head)
return head.min;
return -1;
}
}
作者：windliang
链接：https://leetcode-cn.com/problems/min-stack/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-38/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。腾讯云开发者
