剑指offer第30题 包含min函数的栈

文章目录

问题描述：解题思路：代码实现：

问题描述：

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.min(); --> 返回 -2.

解题思路：

  本题的难点在于时间复杂度的要求，不能通过遍历的方式进行获取最小值。我们可以建立一个辅助栈b用于存储最小值；由于栈先进后出的特点，辅助栈并不需要存储主栈a中所有的元素然后进行排序。   当压入的元素是最小值，或者当前辅助栈为空时，辅助栈b进行压入元素。   当弹出元素时，将b的栈顶元素和a的栈顶元素进行比较，如果相等则b也进行弹出。因为栈是先进后出的，所以不必担心a弹出其他元素时会改变当前的最小值。并且当b弹出栈顶元素时，b的下一个栈顶元素一定是a剩余元素中的最小值。

代码实现：

import java.util.Stack; public class t30MinStack { Stack<Integer> a; Stack<Integer> b; public t30MinStack() { a = new Stack<Integer>(); //主栈 b = new Stack<Integer>(); //辅助栈，用于存储最小的数据 } public void push(int x) { a.push(x); //由于栈先进后出的特性，辅助栈并不需要将a中所有的元素都进行存储然后排序 //只有压入的元素小于所有元素的时候才进行记录 //如果新压入的值小于当前的最小值，则b压入x if(b.empty() || x<=b.peek()) { //注意条件要包含等号，防止出现重复的情况 b.push(x); } } public void pop() { //如果当前弹出的值是最小值，则b也把栈顶元素弹出 //由于栈是先进后出的顺序出栈，所以把当前最小值（b的栈顶）弹出后，下一个栈顶元素一定是a剩下元素的最小值 if(a.pop().equals(b.peek())) { b.pop(); } } public int top() { return a.peek(); } public int min() { return b.peek(); } }

提交结果：