当前位置: 首页> 教育> 高考 > 【剑指 offer】包含min函数的栈

【剑指 offer】包含min函数的栈

时间:2025/7/11 9:35:12来源:https://blog.csdn.net/m0_67660672/article/details/141188227 浏览次数:0次

目 录

描述:

定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的 min 函数,输入操作时保证 pop、top 和 min 函数操作时,栈中一定有元素。

此栈包含的方法有:

  • push(value): 将 value 压入栈中
  • pop(): 弹出栈顶元素
  • top(): 获取栈顶元素
  • min(): 获取栈中最小元素

解题思路:

很容易想到,在栈内部保存 min 变量,每次更新的时候,都对 min 变进行更新。
但是,问题是:如果想拿出第二小,第三小的值怎么拿?用上面的办法就不行了
为了满足通用,我们使用一个辅助栈,内部保存元素的个数和数据栈完全一样,不过,辅助栈内部永远保存本次入栈的数为所有数据的最小值(注意:辅助栈内部元素可能会出现“必要性”重复)
我们这里是为了实现算法, 所以就不从 0 开始实现 stack 了
题面说了,保证测试中不会当栈为空的时候,对栈调用pop()或者min()或者top()方法,所以,后面的代码对空的检验可有可无

import java.util.Stack;
public class Solution {private Stack<Integer> data_stack = new Stack<>();//数据栈private Stack<Integer> min_stack = new Stack<>();//辅助栈public void push(int node) {data_stack.push(node);if(min_stack.empty() || node < min_stack.peek()){min_stack.push(node);}else{//!min_stack.empty() & node >=min_stack.peek()min_stack.push(min_stack.peek());}}public void pop() {data_stack.pop();min_stack.pop();}public int top() {return data_stack.peek();}public int min() {return min_stack.peek();}
}
关键字:【剑指 offer】包含min函数的栈

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: