Leetcode155.最小栈

1.题目

设计一个支持 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.

2.解答

1.使用辅助栈

在之前的一篇文章设计一个有getMin功能的栈中,已经介绍了使用一个辅助栈进行保存每一次操作后的最小值,所以看到题就直接提交通过了

class MinStack {
    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;
    /** initialize your data structure here. */
    public MinStack() {
        stackData = new Stack<>();
        stackMin = new Stack<>();
    }
    
    public void push(int x) {
        stackData.push(x);
        if(stackMin.isEmpty() || x <= stackMin.peek())
            stackMin.push(x);       
    }
    
    public void pop() {
        if(stackData.isEmpty())
            throw new RuntimeException("stack is null");
        int result = stackData.pop();
        if(result == stackMin.peek())
            stackMin.pop();
    }
    
    public int top() {
        if(stackData.isEmpty())
            throw new RuntimeException("stack is null");
        return stackData.peek();
    }
    
    public int getMin() {
        if(stackMin.isEmpty())
            throw new RuntimeException("stack is null");
        return stackMin.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();
 */

但是显然这种方法在提交的时候自己已经发现问题了,就是多使用一个栈,占用的内存很大,还是需要考虑其他的方法

2.简洁无辅助栈

这种方法的思想是:在进栈是维护一个最小值min,如果进栈值x大于min,正常进栈,如果x <= min,那么将min也压入栈中,然后x入栈,更新最小值,出栈时判断是否满足stack.pop() <= min,满足继续执行min = stack.pop(),既完成了出栈两个元素,又更新了最小值

class MinStack {
    private Stack<Integer> stack;
    private int min = Integer.MAX_VALUE;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
    }
    
    public void push(int x) {
        if(x <= min){
            stack.push(min);
            min = x;
        }
        stack.push(x);
    }
    
    public void pop() {
        if(stack.pop() <= min){
            min = stack.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return min;
    }
}

/**
 * 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();
 */

但是在提交结果中,

image

发现和上面使用辅助站内存消耗是一样的,那么我认为就是测试栈中增加的多余元素和辅助栈的大小差不多大小的原因

3.简洁无辅助栈_2

第二种方法解决的主要问题就是,可以使用一个min来保存当前栈最小值,但是当min出栈之后怎么办,并没有记录上一次的min,第二种方法将上一次的min同样入栈,接下来还有一种保存上一次 的min的思路,就是保存他们发生的关系:

入栈 3,存入 3 - 3 = 0
|   |   min = 3
|   |     
|_0_|    
stack   

入栈 5,存入 5 - 3 = 2
|   |   min = 3
| 2 |     
|_0_|    
stack  

入栈 2,因为出现了更小的数,所以我们会存入一个负数,这里很关键
也就是存入  2 - 3 = -1, 并且更新 min = 2 
对于之前的 min 值 3, 我们只需要用更新后的 min - 栈顶元素 (-1) 就可以得到    
| -1|   min = 2
| 5 |     
|_3_|    
stack  

入栈 6,存入  6 - 2 = 4
| 4 |   min = 2
| -1| 
| 5 |     
|_3_|    
stack  

出栈,返回的值就是栈顶元素 4 加上 min,就是 6
|   |   min = 2
| -1| 
| 5 |     
|_3_|    
stack  

出栈,此时栈顶元素是负数,说明之前对 min 值进行了更新。
入栈元素 - min = 栈顶元素,入栈元素其实就是当前的 min 值 2
所以更新前的 min 就等于入栈元素 2 - 栈顶元素(-1) = 3
|   | min = 3
| 5 |     
|_3_|    
stack     

实现代码:

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;
	}
}

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://hadoo666.top/archives/leetcode155最小栈md