leetcode热题HOT 155. 最小栈

本文主要是介绍leetcode热题HOT 155. 最小栈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、问题描述：

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

二、解决方法：

1、思路分析：该最小栈使用两个栈来实现：一个普通的栈（stack）用于存储元素，另一个辅助栈（minStack）用于存储当前栈中的最小元素。

①在构造函数中，初始化两个栈，并在辅助栈中压入一个初始值 Integer.MAX_VALUE，保证了在初始状态下，最小栈的 getMin() 操作可以返回正确的最小值。
②push(int val) 方法将元素压入普通栈，并将当前栈中的最小值与新压入的值进行比较，将较小值压入辅助栈中，保持辅助栈的栈顶始终为当前栈中的最小元素。
③pop() 方法从普通栈中弹出元素，并同时从辅助栈中弹出对应的最小元素，以保持两个栈的同步。
④top() 方法直接返回普通栈的栈顶元素，而 getMin() 方法则返回辅助栈的栈顶元素，即当前栈中的最小元素。

2、代码示例

class MinStack {// 普通栈，用于存储元素Deque<Integer> stack;// 辅助栈，用于存储当前栈中的最小元素Deque<Integer> minStack;// 构造函数，初始化两个栈，并在辅助栈中压入一个初始值 Integer.MAX_VALUEpublic MinStack() {stack = new LinkedList<>();minStack = new LinkedList<>();minStack.push(Integer.MAX_VALUE);}// 元素入栈操作public void push(int val) {// 将元素压入普通栈stack.push(val);// 将当前栈中的最小值与新压入的值进行比较，并将较小值压入辅助栈中，保持辅助栈的栈顶始终为当前栈中的最小元素minStack.push(Math.min(minStack.peek(), val));}// 元素出栈操作public void pop() {// 从普通栈中弹出元素stack.pop();// 同时从辅助栈中弹出对应的最小元素，以保持两个栈的同步minStack.pop();}// 获取栈顶元素操作public int top() {// 直接返回普通栈的栈顶元素return stack.peek();}// 获取当前栈中的最小元素操作public int getMin() {// 返回辅助栈的栈顶元素，即当前栈中的最小元素return minStack.peek();}
}

3、 时间复杂度分析：

①push(int val) 方法的时间复杂度为 O(1)，因为它只是在两个栈中进行一些基本的操作，不会涉及遍历或循环。
②pop() 方法的时间复杂度也是 O(1)，因为它只是从两个栈中弹出元素，并没有涉及遍历或循环。
③top() 和 getMin() 方法也都是 O(1)，因为它们只是返回栈顶元素，并不会对栈中的元素进行修改或遍历。

这篇关于leetcode热题HOT 155. 最小栈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---