150. 逆波兰表达式求值
解题思路
- 常见的中序表达式可以看作对二叉树的后序遍历--左右中
- 栈的计算过程：遇见数字就加入到栈里，遇见操作符就把数字取出做一个计算，再把数字加入栈里
- 栈中最后一个数字就是计算结果
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new LinkedList<>();
for(String s : tokens){
if("+".equals(s)){
stack.push(stack.pop() + stack.pop());
}else if("*".equals(s)){
stack.push(stack.pop() * stack.pop());
}else if("-".equals(s)){
stack.push(-stack.pop() + stack.pop());
}else if("/".equals(s)){
int temp1 = stack.pop();
int temp2 = stack.pop();
stack.push(temp2 / temp1);
}else{
stack.push(Integer.valueOf(s));
}
// - 和 /要特殊处理是因为，这两个是不可交换的，所以必须用正确的顺序处理
}
return stack.pop();
}
}
239. 滑动窗口最大值 （有点难度，可能代码写不出来，但一刷至少需要理解思路）
解题思路
需要自己去构造单调递减队列：滑动窗口移动的时候，就pop左边遗弃的元素，push右边新加入的元素，然后返回每个最大值
-
如果有一个队列 【1，3，-1，-3，5，3，2，1】
- 第一轮：加入1；加入3，前面1<3，就弹出1，要始终保持出口处就剩下最大值，每次getMaxValue就剩出口处元素即可
- 【3，-1，-3】
- 【5】 需要先pop当前队列中的最大值3，push5，因为5比前面的元素都大，所以pop前面所有元素
- 【5，3】 3 没有5大，所以能加入
- 【5，3，2】 2 没有其他的元素大，所以能进入
- 【3，2，1】 因为滑动窗口滑出去了，所以把顶端的5pop，当前最大的就是3
原则：push进来的元素比前面的都大，则前面的都要排除，直到前面的元素没有加入的大为止
class Solution {
private class MyQueue { // 单调队列（从大到小）
Deque<Integer> deque = new LinkedList<>();
// 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
// 同时pop之前判断队列当前是否为空。
void pop(int value) {
if (!deque.isEmpty() && value == deque.peekFirst()) {
deque.pollFirst();
}
}
// 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
// 这样就保持了队列里的数值是单调从大到小的了。
void push(int value) {
while (!deque.isEmpty() && value > deque.peekLast()) {
deque.pollLast();
}
deque.offerLast(value);
}
// 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
int front() {
return deque.peekFirst();
}
}
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) {
return new int[0];
}
MyQueue que = new MyQueue();
int[] result = new int[nums.length - k + 1];
int index = 0;
// 先将前k的元素放进队列
for (int i = 0; i < k; i++) {
que.push(nums[i]);
}
// 记录前k的元素的最大值
result[index++] = que.front();
for (int i = k; i < nums.length; i++) {
que.pop(nums[i - k]); // 滑动窗口移除最前面元素
que.push(nums[i]); // 滑动窗口前加入最后面的元素
result[index++] = que.front(); // 记录对应的最大值
}
return result;
}
}
照着C++代码写的，还要复习。
347.前 K 个高频元素 （有点难度，可能代码写不出来，一刷至少需要理解思路）
大/小顶堆的应用， 在C++中就是优先级队列
本题是 大数据中取前k值 的经典思路，了解想法之后，不算难。
题目链接/文章讲解/视频讲解
思路
这道题难点在于：1.统计元素出现的频率；2.对频率进行排序，并求前k个高频元素
- 用Map: key存放元素，value是出现的次数，然后对value进行排序
- 但是不需要对所有元素都进行排序，只需要维护前k个有序集合。所以用Map遍历，堆里就维持k个元素
数据结构
- 大顶堆、小顶堆
擅长在数据集中求高频/低频操作
使用小顶堆，可以在pop时弹出较小的元素，堆里留下的就是大的元素
小顶堆（Min-Heap）是一种完全二叉树，它具有以下特性：
- 根节点最小：对于任意节点
i，节点i的值总是不大于其子节点的值。即，堆顶元素是整个堆中最小的元素。- 完全二叉树：小顶堆必须是一棵完全二叉树，所有的层（除了最后一层）都是满的，最后一层从左到右填充。
小顶堆的操作：
- 插入操作：
- 插入新元素时，将元素放在堆的最后，然后向上调整，使其符合小顶堆的特性。
- 向上调整的过程称为“上滤（Percolate Up）”或“堆化（Heapify Up）”。
- 删除堆顶元素：
- 删除堆顶（最小元素）时，将堆的最后一个元素放到堆顶，然后向下调整，使其符合小顶堆的特性。
- 向下调整的过程称为“下滤（Percolate Down）”或“堆化（Heapify Down）”。
小顶堆的用途：
小顶堆常用于需要快速找到最小元素的场景，例如：
- 优先队列：在优先队列中，小顶堆可以快速找到优先级最高（最小值）的元素。
- 排序算法：堆排序（Heap Sort）可以利用小顶堆进行升序排序。
- Top K 问题：在寻找前
K个最大元素或前K个最小元素时，可以使用小顶堆进行高效处理。
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// 统计元素出现频率
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
// 定义一个小顶堆，大小为 k
PriorityQueue<Map.Entry<Integer, Integer>> priQueue = new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
return o1.getValue() - o2.getValue(); // 小顶堆，按频率升序排序
}
});
// 用固定大小为 k 的小顶堆，扫描所有频率的数值
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
priQueue.offer(entry);
if (priQueue.size() > k) {
priQueue.poll(); // 堆的大小大于 k，则弹出堆顶元素
}
}
// 找出前 k 个高频元素，因为小顶堆先弹出的是最小的，所以直接输出到数组
int[] result = new int[k];
int index = 0;
while (!priQueue.isEmpty()) {
result[index++] = priQueue.poll().getKey();
}
return result;
}
}
总结
https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E6%80%BB%E7%BB%93.html
