剑指 Offer 30. 包含min函数的栈
2021/8/9 23:07:21
本文主要是介绍剑指 Offer 30. 包含min函数的栈,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
剑指 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(); } }
这篇关于剑指 Offer 30. 包含min函数的栈的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现