剑指 Offer 30. 包含min函数的栈
2024-10-19 10:18:25
剑指 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.
提示：
各函数的调用总次数不超过 20000 次
做题思路：
这道题主要是要了解到借助辅助栈，然后依次把minStack中的数值依次非严格排序放在辅助栈则栈minStack最小的值始终对应着辅助栈栈顶元素。
public class Solution {
Stack<Integer> a = new Stack<>();
Stack<Integer> b = new Stack<>();
public void push(int node) {
a.add(node);
if (b.isEmpty() || b.peek() >= node) {//如果b栈为空或者b的顶点大于node，则把node加入b栈
b.add(node);
}
}
public void pop() {
if (a.pop().equals(b.peek()))//如果a栈退出的值等于b栈顶的值，则栈b也退出栈
b.pop();
}
public int top() {
return a.peek();//直接返回栈a的栈顶元素
}
public int min() {
return b.peek();//直接返回栈b的栈顶元素
}
}
public class MinStack {
/** initialize your data structure here.
这个主要是在push的方法中对栈b遇到的x大于栈b以后所进行的变形*/
Stack<Integer> a, b;
public MinStack() {
a = new Stack<>();
b = new Stack<>();
}
public void push(int x) {
if (b.isEmpty() || b.peek() > x) {
b.add(x);
} else {//如果b栈的顶值小于x，则把相同的b.peek()放入b栈
b.add(b.peek());
}
a.add(x);
}
public void pop() {
a.pop();
b.pop();
}
public int top() {
return a.peek();
}
public int min() {
return b.peek();
}
}
最新文章
- sublime text2 bracketHighLighter 配置
- JS中误用/g导致的正则test()无法正确重复执行
- dmesg 显示内核消息
- jQuery中的height()、innerheight()、outerheight()的区别总结
- 织梦DedeCms用SQL语句调用数据库任意内容
- Sublime Text2不自动打开最近的项目
- Wish | IT桔子
- #数论-模运算#POJ 1150、1284、2115
- Hadoop详解一：Hadoop简介
- [LeetCode] Longest Palindromic Subsequence 最长回文子序列
- ASP.NET WebApi OWIN 实现 OAuth 2.0（自定义获取 Token）
- 初识Python.day2
- Javaweb实现对mongodb的增删改查（附带源代码）
- Android典型界面设计(7) ——DrawerLayout+Fragement+ViewPager+PagerTabStrip实现双导航
- vba 调用 countif 函数问题
- 多态概念，C++
- 使用Log4net创建日志及简单扩展
- 阿里巴巴Java编码规范，来测测你能得多少分
- python中几个实用的文件操作
- java 连接mysql增删改查