力扣 - 剑指 Offer 30. 包含min函数的栈
2021/11/9 6:11:14
本文主要是介绍力扣 - 剑指 Offer 30. 包含min函数的栈,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
剑指 Offer 30. 包含min函数的栈
思路1
- 使用一个辅助栈
min_stack
,用来维护栈的最小的元素 - 每次添加元素入栈时候,
data_stack
和min_stack
都要同时维护 data_stack
按照正常的栈压入和弹出顺序,但是min_stack
栈不一样,因为要能获取当前栈的最小元素:- 如果栈是空的,直接入栈
- 如果栈不是空的,分两种情况:
- 待入栈的元素
x
小于min_stack
栈顶的元素,此时直接将x
压入min_stack
栈 - 待入栈的元素
x
大于min_stack
栈顶的元素,此时将当前栈顶元素再次压入栈顶
- 待入栈的元素
代码
class MinStack { LinkedList<Integer> data_stack; // min_stack为辅助栈 LinkedList<Integer> min_stack; public MinStack() { // 初始化 data_stack = new LinkedList<>(); min_stack = new LinkedList<>(); } public void push(int x) { data_stack.push(x); // 入栈的时候要判断辅助栈是否为空,空的话直接push即可 if (!min_stack.isEmpty()) { // 判断待入栈的元素x是否大于min_stack栈顶元素,如果小于直接入栈;若大于,则将原来栈顶的元素再次入栈一次 if (x < min_stack.peek()) { min_stack.push(x); } else { min_stack.push(min_stack.peek()); } } else { min_stack.push(x); } } public void pop() { // 如果pop的话直接弹出去 // 这里不用担心min_stack辅助栈的最小元素被pop出去,因为min_stack和data_stack是一一对应的,同时pop出去对获取当前栈的最小值没有影响 data_stack.pop(); min_stack.pop(); } public int top() { // 查看当前栈的栈顶也是直接peek return data_stack.peek(); } public int min() { // 辅助栈的栈顶元素就是当前栈中的最小的元素 return min_stack.peek(); } }
复杂度分析
- 时间复杂度:\(O(1)\)
- 空间复杂度:\(O(N)\)
这篇关于力扣 - 剑指 Offer 30. 包含min函数的栈的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-20接口模块封装入门教程
- 2024-09-20请求动作封装入门教程
- 2024-09-20登录鉴权学习:新手入门教程
- 2024-09-20后台管理开发学习:新手入门指南
- 2024-09-20后台管理系统开发学习:从入门到实践
- 2024-09-20后台开发学习:从入门到初级实战指南
- 2024-09-20后台综合解决方案学习:从入门到实践
- 2024-09-20接口模块封装学习入门指南
- 2024-09-20请求动作封装学习:新手入门教程
- 2024-09-20登录鉴权入门:打造安全的用户认证系统