算法笔记|Day10栈与队列II
☆☆☆☆☆leetcode 150. 逆波兰表达式求值
题目分析
1.依次遍历各个元素，若不为运算符则入栈，若为运算符则取前两个元素作相应运算，直至结束；
2.时间复杂度为O(n)，空间复杂度为O(n)。
代码
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> deque=new LinkedList();
for(String s:tokens){
if(!("+".equals(s)||"-".equals(s)||"*".equals(s)||"/".equals(s))){
deque.push(Integer.valueOf(s));
}else{
int num1=deque.pop(),num2=deque.pop();
if("+".equals(s)){
deque.push(num2+num1);
}else if("-".equals(s)){
deque.push(num2-num1);
}else if("*".equals(s)){
deque.push(num2*num1);
}else if("/".equals(s)){
deque.push(num2/num1);
}
}
}
return deque.pop();
}
}
☆☆☆☆☆leetcode 239. 滑动窗口最大值
题目分析
1.考虑单调队列，i为nums下标，是要在[i-k+1, i]中选到最大值，只需要保证：① 队列头结点需要在[i -k+1, i]范围内，不符合则要弹出，②每次放进去的数字要比末尾的都大，否则也弹出，③当i增长到符合第一个k范围的时候，每滑动一步将队列头节点放入结果；
2.时间复杂度为O(n)，空间复杂度为O(k)。
代码
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deque=new LinkedList();
int n=nums.length;
int res[]=new int[n-k+1];
int index=0;
for(int i=0;i<n;i++){
while(!deque.isEmpty()&&deque.peek()<i-k+1)
deque.poll();
while(!deque.isEmpty()&&nums[deque.peekLast()]<nums[i])
deque.pollLast();
deque.add(i);
if(i>=k-1){
res[index]=nums[deque.peek()];
index++;
}
}
return res;
}
}
☆☆☆☆☆leetcode 347.前 K个高频元素（待补充）
题目分析
代码