java-leetcode面试题解Stack之第155题最小栈-题解.zip

在Java编程领域，LeetCode是一个非常受欢迎的在线平台，它提供了大量的编程题目，旨在帮助开发者提升算法技能，准备求职面试。本题解聚焦于LeetCode第155题——"最小栈"，这是一个与数据结构栈相关的面试常考题目。通过解决这道题，我们可以深入理解栈的特性和如何利用栈优化问题的解决方案。 最小栈问题的基本要求是设计一个支持以下操作的数据结构： 1. `push(x)`：将元素x推入栈中。 2. `pop()`：移除栈顶元素。 3. `top()`：获取栈顶元素。 4. `getMin()`：任何时候都能立刻获取栈中的最小元素。 传统的栈只提供基本的`push`、`pop`、`top`操作，但不支持快速获取最小元素。为了解决这个问题，我们可以采用以下策略： 1. 使用两个栈，一个普通栈（我们称为`mainStack`）用于常规的`push`、`pop`和`top`操作，另一个栈（我们称为`minStack`）用于存储当前栈中的最小元素。 2. 当我们执行`push(x)`时，同时将x压入`mainStack`和`minStack`。如果`minStack`为空或x小于`minStack`的栈顶元素，那么`x`也应成为`minStack`的栈顶元素。 3. 执行`pop()`时，两个栈都弹出顶部元素。 4. `top()`操作只需返回`mainStack`的栈顶元素。 5. `getMin()`操作则直接返回`minStack`的栈顶元素，即为当前栈中的最小元素。 以下是使用Java实现这个最小栈的代码示例： ```java public class MinStack { private Stack<Integer> mainStack; private Stack<Integer> minStack; public MinStack() { mainStack = new Stack<>(); minStack = new Stack<>(); } // 入栈操作 public void push(int x) { mainStack.push(x); if (minStack.isEmpty() || x <= minStack.peek()) { minStack.push(x); } } // 出栈操作 public void pop() { if (!mainStack.isEmpty()) { mainStack.pop(); if (mainStack.isEmpty()) { minStack.clear(); } else if (mainStack.peek() == minStack.peek()) { minStack.pop(); } } } // 获取栈顶元素 public int top() { return mainStack.peek(); } // 获取最小元素 public int getMin() { return minStack.peek(); } } ``` 这个解决方案的时间复杂度为O(1)，因为所有操作都在常量时间内完成。空间复杂度也是O(n)，其中n是栈中元素的数量，因为我们需要额外的空间来存储`minStack`。 在面试中，这种问题通常用来考察候选人的数据结构和算法基础，以及他们解决问题的创新能力。通过深入理解并实践最小栈的设计，开发者可以增强自己的编程技巧，更好地应对实际工作中的挑战。在准备求职面试时，多练习类似的LeetCode题目，有助于提升面试表现，增加获得理想职位的机会。