Java实现LeetCode第155题最小栈解析

Java是一种广泛使用的面向对象的编程语言，它因其平台无关性、对象导向和简单性而受到许多开发者的喜爱。在求职面试中，特别是在软件工程师的面试中，算法和数据结构的知识往往占有重要位置。LeetCode是一个流行的在线编程挑战和面试准备平台，提供了一系列编程问题，帮助应聘者为技术面试做准备。其中，第155题是最小栈的设计问题，这是一个考察应聘者对栈（Stack）数据结构以及辅助结构设计能力的经典面试题。 栈是一种后进先出（LIFO, Last In First Out）的数据结构，只允许在栈的一端进行添加（push）或移除（pop）操作。最小栈是一种特殊的栈，它额外要求能够提供当前栈内所有元素中的最小值。这意味着除了正常的栈操作之外，最小栈需要支持一个常数时间复杂度的操作来获取当前栈内的最小值。 在Java中实现最小栈，一种常见的方法是使用两个栈：一个普通的栈用于存储所有的元素，另一个辅助栈用于存储到目前为止遇到的最小元素。每次进行push和pop操作时，都要相应地更新辅助栈的状态，以确保它能够反映当前的最小值。例如，当新元素比当前最小值小或者两个栈都为空时，新元素就应该被压入辅助栈中；当弹出的元素是当前的最小元素时，辅助栈也应该弹出栈顶元素。 下面是使用Java实现最小栈类的一个示例代码： ```java class MinStack { private Stack<Integer> stack; private Stack<Integer> minStack; public MinStack() { stack = new Stack<>(); minStack = new Stack<>(); } public void push(int x) { stack.push(x); if (minStack.isEmpty() || x <= minStack.peek()) { minStack.push(x); } } public void pop() { if (stack.isEmpty()) { throw new IllegalStateException("栈为空"); } int popVal = stack.pop(); if (popVal == minStack.peek()) { minStack.pop(); } } public int top() { if (stack.isEmpty()) { throw new IllegalStateException("栈为空"); } return stack.peek(); } public int getMin() { if (minStack.isEmpty()) { throw new IllegalStateException("栈为空"); } return minStack.peek(); } } ``` 在这个类中，`stack`是常规栈，用来存储所有元素，而`minStack`是辅助栈，用来存储所有遇到的最小元素。在`push`方法中，当新元素小于等于当前最小元素时，新元素会被压入`minStack`。在`pop`方法中，当被弹出的元素等于`minStack`的栈顶元素时，表示这个元素是当前最小元素，因此`minStack`也要进行弹出操作。 对于求职者来说，掌握最小栈的设计思路和实现方法是很有帮助的，因为这可以展示他们解决实际问题的能力，并且能够使用栈这种数据结构来优化操作性能。熟悉常见的数据结构及其操作对于通过编程面试至关重要。 由于最小栈的题解涉及到多个知识点，因此这个问题在面试中被频繁使用，它不仅考察编程能力，还考察应聘者对数据结构深入理解和应用能力。掌握这类题目的解决方案，无疑有助于提高求职者在技术面试中的表现。