栈与队列能解决哪些经典问题?每个问题都在我主页中可以找到,欢迎大家关注~~
(1)括号匹配问题(栈)
(2)字符串去重问题(栈)
(3) 逆波兰表达式问题(栈)
(4)下一个更大元素(单调栈)
(5)接雨水(单调栈)
(6)滑动窗口最大值问题(单调队列)
(7)前K个出现次数最多的元素问题(优先级队列)
(8)栈实现队列
(9)队列实现栈
一.题解
给定一个整数数组 temperatures
,表示每天的温度,返回一个数组 answer
,其中 answer[i]
是指对于第 i
天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0
来代替。
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
Deque<Integer> deque=new LinkedList<Integer>();
int[] res=new int[temperatures.length];
for(int i=0;i<temperatures.length;i++){
int num=temperatures[i];
while(!deque.isEmpty()&&num>temperatures[deque.peek()]){
int index=deque.pop();
res[index]=i-index;
}
deque.push(i);
}
return res;
}
}
二.栈的基础知识
栈最显著特点就是:先进后出
1.Java中栈的常见实现类:
最基础实现:Stack<Integer> stack=new Stack<>();
双端队列实现:Deque<Integer> stack=new LinkedList<>();
2.栈的常用方法
push(x) — 将一个元素放入队列的尾部。
pop() — 从队列首部移除元素。
peek() — 返回队列首部的元素。
empty() — 返回队列是否为空。
三.队列的基础知识
队列最显著特点就是:先进先出
1.Java中队列的常见实现类:
普通队列:Queue<Integer> queue=new LinkedList<>();
双端队列:Deque<Integer> queue=new LinkedList<>();
优先级队列:PriorityQueue<Integer> queue=new PriorityQueue<>();
2.队列的常用方法
add 增加一个元索 如果队列已满,则抛出一个IIIegaISlabEepeplian异常
remove 移除并返回队列头部的元素 如果队列为空,则抛出一个NoSuchElementException异常
element 返回队列头部的元素 如果队列为空,则抛出一个NoSuchElementException异常
size 元素个数
offer 添加一个元素并返回true 如果队列已满,则返回false
poll 移除并返问队列头部的元素 如果队列为空,则返回null
peek 返回队列头部的元素 如果队列为空,则返回null
put 添加一个元素 如果队列满,则阻塞
take 移除并返回队列头部的元素 如果队列为空,则阻塞
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/116048.html