155. 最小栈


155. 最小栈

难度简单 820
设计一个支持 pushpoptop 操作,并能在常数时间内检索到最小元素的栈。

  • 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.

提示:

  • poptopgetMin 操作总是在 非空栈 上调用。
class MinStack {

    Deque<Integer> xStack;
    Deque<Integer> minStack;

    public MinStack() &#123;
        xStack = new LinkedList<Integer>();
        minStack = new LinkedList<Integer>();
        minStack.push(Integer.MAX_VALUE);//
    &#125;

    public void push(int x) &#123;
        xStack.push(x);
        minStack.push(Math.min(minStack.peek(), x));
    &#125;

    public void pop() &#123;
        xStack.pop();
        minStack.pop();
    &#125;

    public int top() &#123;
        return xStack.peek();
    &#125;

    public int getMin() &#123;
        return minStack.peek();
    &#125;

// 作者:LeetCode-Solution
// 链接:https://leetcode-cn.com/problems/min-stack/solution/zui-xiao-zhan-by-leetcode-solution/
&#125;

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

解析

辅助栈
要做出这道题目,首先要理解栈结构先进后出的性质。
对于栈来说,如果一个元素 a 在入栈时,栈里有其它的元素 b, c, d,那么无论这个栈在之后经历了什么操作,只要 a 在栈中,b, c, d 就一定在栈中,因为在 a 被弹出之前,b, c, d 不会被弹出。
因此,在操作过程中的任意一个时刻,只要栈顶的元素是 a,那么我们就可以确定栈里面现在的元素一定是 a, b, c, d。
那么,我们可以在每个元素 a 入栈时把当前栈的最小值 m 存储起来。在这之后无论何时,如果栈顶元素是 a,我们就可以直接返回存储的最小值 m。
image.png


文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
69. x 的平方根 69. x 的平方根
69. x 的平方根难度简单 605实现 int sqrt(int x) 函数。计算并返回 x 的平方根,其中 x *是非负整数。由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。*示例 1:**输入: 4输出: 2 示例 2:输
下一篇 
20. 有效的括号 20. 有效的括号
20. 有效的括号难度简单 2197给定一个只包括 '(',')','{','}','[',']' 的字符串 s,判断字符串
  目录