第五章 栈与队列part02
150. 逆波兰表达式求值
本题不难，但第一次做的话，会很难想到，所以先看视频，了解思路再去做题
题目链接/文章讲解/视频讲解：https://programmercarl.com/0150.%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC.html
import java.util.*;
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> deque = new LinkedList<>();
int size = tokens.length;
for(int i = 0; i < size; i ++){
if(tokens[i].equals("+")){// 必须比较值
int x = deque.pop();
int y = deque.pop();
deque.push(x + y);
}else if(tokens[i].equals("*")){
int x = deque.pop();
int y = deque.pop();
deque.push(x * y);
}else if(tokens[i].equals("/")){
int x = deque.pop();
int y = deque.pop();
deque.push(y / x);
}else if(tokens[i].equals("-")){
int x = deque.pop();
int y = deque.pop();
deque.push(y - x);
}else{
deque.push(Integer.valueOf(tokens[i]));
}
}
return deque.pop();
}
}
239. 滑动窗口最大值 （有点难度，可能代码写不出来，但一刷至少需要理解思路）
之前讲的都是栈的应用，这次该是队列的应用了。
本题算比较有难度的，需要自己去构造单调队列，建议先看视频来理解。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html
我的答案：
import java.util.*;
class MyQueue{
Deque<Integer> deque;
public MyQueue(){
deque = new LinkedList<>();
}
public void pop(int val){
if(!deque.isEmpty() && deque.peek() == val){
deque.removeFirst();
}
}
public void push(int val){
while (!deque.isEmpty() && val > deque.peekLast()){
deque.removeLast();
}
deque.addLast(val);
}
public int peek(){
return deque.peekFirst();
}
}
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length - k + 1;
int[] result = new int[len];
MyQueue mq = new MyQueue();
int count = 0;
int num = 0;
for(int i = 0; i < nums.length; i ++){
if(count < k ){
if(count == 0){
mq.pop(nums[i]);
}
mq.push(nums[i]);
count ++;
}else{
result[num++] = mq.peek();
count = 0;
}
}
return result;
}
}
错误用例：
nums =[1,3,-1,-3,5,3,6,7] k =3
输出
[3,6,0,0,0,0]
预期结果
[3,3,5,5,6,7]
修改 : 注意到后来每一次都要检查pop下
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length - k + 1;
int[] result = new int[len];
MyQueue mq = new MyQueue();
int count = 0;
int num = 0;
for(int j = 0; j < k; j ++){
mq.push(nums[j]);
}
result[num++] = mq.peek();
for(int i = k; i < nums.length; i ++){
mq.pop(nums[i]);
mq.push(nums[i]);
result[num++] = mq.peek();
}
return result;
}
}
错误用例：
ums =[1,-1] k = 1
输出
[1,1]
预期结果
[1,-1]
import java.util.*;
class MyQueue{
Deque<Integer> deque;
public MyQueue(){
deque = new LinkedList<>();
}
public void pop(int val){
if(!deque.isEmpty() && deque.peekFirst() == val){
deque.removeFirst();
}
}
public void push(int val){
while (!deque.isEmpty() && val > deque.peekLast()){
deque.removeLast();
}
deque.addLast(val);
}
public int peek(){
return deque.peekFirst();
}
}
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length - k + 1;
int[] result = new int[len];
MyQueue mq = new MyQueue();
int count = 0;
int num = 0;
for(int j = 0; j < k; j ++){
mq.push(nums[j]);
}
result[num++] = mq.peek();
for(int i = k; i < nums.length; i ++){
mq.pop(nums[i-k]);// 每次pop 检查的元素应该是当前元素k个前的元素
mq.push(nums[i]);
result[num++] = mq.peek();
}
return result;
}
}
ACC
347.前 K 个高频元素 （有点难度，可能代码写不出来，一刷至少需要理解思路）
大/小顶堆的应用， 在C++中就是优先级队列
本题是 大数据中取前k值 的经典思路，了解想法之后，不算难。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// 优先级队列，为了避免复杂 api 操作，pq 存储数组
// lambda 表达式设置优先级队列从大到小存储 o1 - o2 为从小到大，o2 - o1 反之
PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
int[] res = new int[k]; // 答案数组为 k 个元素
Map<Integer, Integer> map = new HashMap<>(); // 记录元素出现次数
for (int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);
for (var x : map.entrySet()) { // entrySet 获取 k-v Set 集合
// 将 kv 转化成数组
int[] tmp = new int[2];
tmp[0] = x.getKey();
tmp[1] = x.getValue();
pq.offer(tmp);
// 下面的代码是根据小根堆实现的，我只保留优先队列的最后的k个，只要超出了k我就将最小的弹出，剩余的k个就是答案
if(pq.size() > k) {
pq.poll();
}
}
for (int i = 0; i < k; i++) {
res[i] = pq.poll()[0]; // 获取优先队列里的元素
}
return res;
}
}
总结
栈与队列做一个总结吧，加油
https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E6%80%BB%E7%BB%93.html
