155. 最小栈【73】

难度等级：简单

上一篇算法：

232. 用栈实现队列【112】

力扣此题地址：

155. 最小栈 - 力扣（Leetcode）

一、题目：155. 最小栈

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

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

二、解题思路：

 剑指 Offer 30. 包含min函数的栈【栈与队列】

剑指 Offer 30. 包含min函数的栈 - 力扣（Leetcode）

~当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；

~当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出；

~在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。

三、代码实现：

class MinStack {
    Stack A, B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    public void push(int x) {
        A.add(x);
        if(B.empty() || B.peek() >= x)
            B.add(x);
    }
    public void pop() {
        if(A.pop().equals(B.peek()))
            B.pop();
    }
    public int top() {
        return A.peek();
    }
    public int getMin() {
        return B.peek();
    }
}