当前位置：首页 > news >正文

剑指offer-20、包含min函数的栈

news 2025/12/24 9:59:01

题⽬描述

定义栈的数据结构，请在该类型中实现⼀个能够得到栈中所含最⼩元素的min 函数（时间复杂度为O（1））。

此栈包含的⽅法有：

push(value) ：将value 压⼊栈中
pop() ：弹出栈顶元素
top() ：获取栈顶元素
min() ：获取栈中最⼩元素

思路及解答

双栈法（推荐，实现简单）

使用两个栈：

主栈：存储所有元素
辅助栈：存储当前主栈中的最小值

push ⼀个元素的时候，都需要push 进datas stack ,但是push 进⼊mins stack 需要满⾜条件：当前的mins stack 是空的，直接放⼊。或者当前的mins stack 的栈顶元素⼤于或者等于push 进来的值。

pop ⼀个元素的时候，如果栈为空则什么都不操作，如果栈不为空，则判断datas 的第⼀个元素是否和mins 的第⼀个元素相等。如果相等的话那么就需要将mins 和datas pop 出去第⼀个元素，否则只需要将datas 的第⼀个元素 pop 出去即可。

public class Solution {private Stack<Integer> datas = new Stack<>();private Stack<Integer> mins = new Stack<>();/*** 将元素压入栈中* @param value 要压入的值*/public void push(int node) {datas.push(node);// 如果辅助栈为空，或新值<=当前最小值，压入辅助栈if (mins.isEmpty()) {mins.push(node);} else {int min = mins.peek();if (node <= min) {mins.push(node);}}}public void pop() {if (datas.isEmpty()) {return;} else {int value = datas.peek();if (value == mins.peek()) {mins.pop();}datas.pop();}}public int top() {if(datas.isEmpty()){return -1;}return datas.peek();}public int min() {if(mins.isEmpty()){return -1;}return mins.peek();}
}

时间复杂度： O(1)
空间复杂度： O(n) ,借助了辅助栈。

差值法

使用一个栈和一个变量minValue：

栈存储差值：存储元素与当前最小值的差值
更新最小值：当遇到更小值时，先存储当前差值(负值)，再更新最小值
恢复前值：pop时如果发现差值为负，说明此处发生过最小值更新，需要恢复前一个最小值

public class Solution {private Stack<Long> stack = new Stack<>();; // 存储差值的栈private long minValue; // 当前最小值public void push(int value) {if (stack.isEmpty()) {minValue = value;stack.push(0L); // 差值为0} else {long diff = (long)value - minValue;stack.push(diff);// 如果差值为负，说明value是新的最小值if (diff < 0) {minValue = value;}}}public void pop() {if (stack.isEmpty()) {return;}long diff = stack.pop();// 如果差值为负，说明此处更新过最小值，需要恢复前一个最小值if (diff < 0) {minValue = minValue - diff;}}public int top() {if (stack.isEmpty()) {return;}long diff = stack.peek();// 如果差值为负，说明当前栈顶就是最小值if (diff < 0) {return (int)minValue;} else {return (int)(minValue + diff);}}public int min() {if (stack.isEmpty()) {return;}return (int)minValue;}
}