【Leetcode】155. 最小栈

题目描述

// 155. 最小栈

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

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

复制代码

题解

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

// 小顶堆法
// 傻瓜方法，用一个小顶堆minHeap维护stack插入元素的最小值，如果要返回最小值，
// 直接取minHeap的堆顶值即可。
// 
// 执行用时：10 ms, 在所有 Java 提交中击败了12.46%的用户
// 内存消耗：39.9 MB, 在所有 Java 提交中击败了95.60%的用户
import java.util.Stack;
import java.util.PriorityQueue;
class MinStack {
    Stack<Integer> stack;
    PriorityQueue <Integer> minHeap;

    /** initialize your data structure here. */
    public MinStack() {
        this.stack = new Stack<>();
        this.minHeap = new PriorityQueue<>();
    }
    
    public void push(int val) {
        stack.push(val);
        minHeap.add(val);
    }
    
    public void pop() {
        int popVal = stack.pop();
        minHeap.remove(popVal);
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minHeap.peek();
    }
}

复制代码

// 栈维护法
// 用一个栈minRecord来维护最小值，minRecord元素表示在stack的当前元素高度时，
// stack中的最小值为多少。
// 如：
// stack  =  []
// minRecord=[]
// 我们将stack.push(-1)，有：
// stack  =  [-1]
// minRecord=[-1]
// 我们将stack.push(0)，此时minRecord检测到-1还是比0小，有：
// stack  =  [-1, 0]
// minRecord=[-1,-1]
// 我们将stack.push(1)，此时minRecord检测到1还是比-1小，所以在1当前高度的
// stack栈中，最小值还是-1，minRecord有：
// stack  =  [-1, 0, 1]
// minRecord=[-1,-1,-1]
// 如果这时我们stack.pop()，则两边同时pop()，有：
// stack  =  [-1, 0]
// minRecord=[-1,-1]
// 这种机制能够使得minRecord的栈顶一直记录着stack相同栈高度下的最小值。
// 如果我们有stack.push(-5)，minRecord检测到-5比栈顶-1小，则有：
// stack  =  [-1, 0,-5]
// minRecord=[-1,-1,-5]
// 
// 可以看到我们只需要对minRecord的push操作进行一个检测控制即可。
// 如果push的val小于minRecord栈顶，直接push进去，如果val大于minRecord，
// 则minRecord会重复把自己的栈顶元素push进来。记录当前高度stack的最小值。
//
// 执行用时：7 ms, 在所有 Java 提交中击败了80.13%的用户
// 内存消耗：40.2 MB, 在所有 Java 提交中击败了53.17%的用户
class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minRecord;

    /** initialize your data structure here. */
    public MinStack() {
        this.stack = new Stack<>();
        this.minRecord = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if (minRecord.isEmpty()) {
            minRecord.push(val);
        }
        else if (minRecord.peek() < val) {
            minRecord.push(minRecord.peek());
        }
        else if (minRecord.peek() >= val) {
            minRecord.push(val);
        }
    }
    
    public void pop() {
        stack.pop();
        minRecord.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minRecord.peek();
    }
}

复制代码