0%

# Leetcode 155 最小栈(Min Stack) 题解分析

Posted on 2020-12-06 In Java , leetcode , stack , java , stack Views: Views: Disqus:

## 题目介绍

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

## 简要分析

其实现在大部分语言都自带类栈的数据结构，Java 也自带 stack 这个数据结构，所以这个题的主要难点的就是常数级的获取最小元素，最开始的想法是就一个栈外加一个记录最小值的变量就行了，但是仔细一想是不行的，因为随着元素被 pop 出去，这个最小值也可能需要梗着变化，就不太好判断了，所以后面是用了一个辅助栈。

## 代码

    class MinStack {
            // 这个作为主栈
            Stack<Integer> s1 = new Stack<>();
            // 这个作为辅助栈，放最小值的栈
            Stack<Integer> s2 = new Stack<>();
            /** initialize your data structure here. */
            public MinStack() {

            }

            public void push(int x) {
                // 放入主栈
                s1.push(x);
                // 当 s2 是空或者当前值是小于"等于" s2 栈顶时，压入辅助最小值的栈
                // 注意这里的"等于"非常必要，因为当最小值有多个的情况下，也需要压入栈，否则在 pop 的时候就会不对等
                if (s2.isEmpty() || x <= s2.peek()) {
                    s2.push(x);
                }
            }

            public void pop() {
                // 首先就是主栈要 pop，然后就是第二个了，跟上面的"等于"很有关系，
                // 因为如果有两个最小值，如果前面等于的情况没有压栈，那这边相等的时候 pop 就会少一个了，可能就导致最小值不对了
                int x = s1.pop();
                if (x == s2.peek())  {
                    s2.pop();
                }
            }

            public int top() {
                // 栈顶的元素
                return s1.peek();
            }

            public int getMin() {
                // 辅助最小栈的栈顶
                return s2.peek();
            }
        }

Related Posts

- Leetcode 236 二叉树的最近公共祖先(Lowest Common Ancestor of a Binary Tree) 题解分析
- Leetcode 104 二叉树的最大深度(Maximum Depth of Binary Tree) 题解分析
- Leetcode 121 买卖股票的最佳时机(Best Time to Buy and Sell Stock) 题解分析
- Leetcode 105 从前序与中序遍历序列构造二叉树(Construct Binary Tree from Preorder and Inorder Traversal) 题解分析
- Leetcode 2 Add Two Numbers 题解分析

请我喝杯咖啡

WeChat Pay

Alipay

- Post author: Nicksxs
- Post link: https://nicksxs.me/2020/12/06/Leetcode-155-最小栈-Min-Stack-题解分析/
- Copyright Notice: All articles in this blog are licensed under BY-NC-SA unless stating additionally.