当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.155.Min Stack 最小栈

LeetCode.155.Min Stack 最小栈

题目描述

155 Min Stack
https://leetcode-cn.com/problems/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:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

相似题目

LeetCode.155.Min Stack 最小栈
LeetCode.剑指offer.059.最大队列


解题过程

数据栈+最小栈

这道题标准的解法是用两个栈,一个存放数据,一个存放当前最小值,空间换时间。
把两个栈封装在一个栈中,其中的一个栈存放正常的元素,另一个栈 minStack 只存当前最小值。
push:数据栈正常操作。比较当前元素和最小栈minStack的栈顶,比栈顶还小则进栈,否则push原栈顶。
pop:数据栈正常操作。最小栈minStack也pop
getMin:直接返回最小栈栈顶

push,pop,top,getMin 时间复杂度都是 O(1),空间复杂度 O(n)

这里还可以有个优化,最小栈并不和数据栈同步更新,只是每次push遇到小于等于栈顶的才放入。pop时如果出栈的数据就是最小栈栈顶最小栈,则最小栈也pop。

private static class MinStack {
    private Deque<Integer> minStack;
    private Deque<Integer> dataStack;
    /** initialize your data structure here. */
    public MinStack() {
        minStack = new LinkedList<>();
        dataStack = new LinkedList<>();
    }

    public void push(int x) {
        dataStack.push(x);
        minStack.push(minStack.peek() != null && minStack.peek() < x ? minStack.peek() : x);
    }

    public void pop() {
        dataStack.pop();
        minStack.pop();
    }

    public int top() {
        return dataStack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

栈中存储Pair(value, min)

栈中存储当前值 value,和当前最小值 min

栈+最小堆(优先队列)

没想到很好的思路,用 栈 + 优先队列(最小堆) 实现的。

push 优先队列offer O(logn)
pop 优先队列remove(x) O(n)
top O(1)
getMin O(1)
空间复杂度 O(n)

private static class MinStack {
    private Deque<Integer> stack;
    private PriorityQueue<Integer> priorityQueue;

    /** initialize your data structure here. */
    public MinStack() {
        stack = new LinkedList<>();
        // 优先队列,小顶堆,堆顶永远是最小值
        priorityQueue = new PriorityQueue<>();
    }

    public void push(int x) {
        stack.push(x);
        priorityQueue.offer(x);
    }

    public void pop() {
        Integer i = stack.pop();
        // remove(x) 的时间复杂度为O(n)
        priorityQueue.remove(i);
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return priorityQueue.peek();
    }
}

GitHub代码

algorithms/leetcode/leetcode/_155_MinStack.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_155_MinStack.java


上一篇 LeetCode.994.Rotting Oranges 腐烂的橘子

下一篇 LeetCode.088.Merge Sorted Array 合并两个有序数组

阅读
评论
575
阅读预计3分钟
创建日期 2020-03-03
修改日期 2020-05-12
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论