栈｜ Leetcode 155

Leetcode 分类刷题 —— 栈（Stack）

1、题目描述：

Leetcode 155. Min Stack (follow up Leetcode 716 Max Stack 最小栈)

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

2、解题思路：

使用两个栈，一个用于存储元素，另一个用于存储当前的最小值。
在插入元素时，将元素入栈，并将当前最小值与元素比较。如果最小值栈为空或者当前元素小于等于最小值栈顶元素，则将当前元素也入最小值栈。
在弹出元素时，如果栈顶元素等于最小值栈顶元素，则将最小值栈顶元素也出栈。
由于每个元素最多被入栈和出栈各一次，因此时间复杂度是O(1)，空间复杂度是O(n)。

3、代码

import java.util.Stack;

class MinStack {
    private Stack<Integer> stack; // 用来存储元素
    private Stack<Integer> minStack; // 用来存储当前最小值

    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val); // 将元素入栈
        if (minStack.isEmpty() || val <= minStack.peek()) {
            // 如果最小值栈为空或者当前元素小于等于最小值栈顶元素，则将当前元素也入最小值栈
            minStack.push(val);
        }
    }

    public void pop() {
        int val = stack.pop(); // 将栈顶元素出栈
        if (val == minStack.peek()) {
            // 如果栈顶元素等于最小值栈顶元素，则将最小值栈顶元素也出栈
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek(); // 返回栈顶元素
    }

    public int getMin() {
        return minStack.peek(); // 返回最小值栈顶元素
    }
}