Leetcode-155-最小栈

Leecode-155-Min Stack

思路：辅助栈/数据同步

题目描述

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) ——   将元素 x 推入栈中。
pop() ——     删除栈顶的元素。
top() ——     获取栈顶元素。
getMin() —— 检索栈中的最小元素。

示例：

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

Solution：辅助栈和数据栈同步

• 特点：编写简单，不需要考虑一些边界情况（缺点：可能会存储一些多余的元素）
• 规则如下：
  • 辅助栈为空的时候，必须放进来新的数字
  • 新来的数小于等于辅助栈栈顶元素的时候，才放入（这里“等于要考虑进去”，因为出栈的时候，相等的并且是最小值的元素要同步出栈），要不然就放入辅助栈栈顶自己
  • 出栈的时候，辅助栈的栈顶元素要等于数据栈栈顶的元素才出栈

总结：

• 出栈的时候，最小值出栈才同步
• 入栈的时候，最小值入栈才同步

Java

Solution :

import java.util.Stack;

public class MinStack {

    // 数据栈
    private Stack<Integer> data;

    // 辅助栈
    private Stack<Integer> helper;

    /**
     * initialize your data structure here.
     */

    public MinStack(){
        data =   new Stack<>();
        helper = new Stack<>();
    }

    // 思路1：数据栈和辅助栈在任何时候都要同步
    public void push(int x){
        data.add(x);
        if (helper.isEmpty() || helper.peek() >= x){
            helper.add(x);
        }else {
            helper.add(helper.peek());
        }
    }


    public void pop(){
        // 两个栈都需要pop操作
        if (!data.isEmpty()){
            helper.pop();
            data.pop();
        }
    }

    public int top(){
        if (!data.isEmpty()){
            return data.peek();
        }
        throw new RuntimeException("栈元素为空");
    }

    public int getMin(){
        if (!helper.isEmpty()){
            return helper.peek();
        }
        throw new RuntimeException("栈元素为空");
    }

}

测试用例：

public class TestStack {
    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();
    }
}

• 时间复杂度：O(1) 栈的操作
• 空间复杂度：O(n) 需要一个辅助栈的空间

打赏