第十二天休息
代码随想录算法训练第十三天内容：
● 150. 逆波兰表达式求值
● 239. 滑动窗口最大值
● 347.前 K 个高频元素
● 总结
150. 逆波兰表达式求值
根据 逆波兰表示法，求表达式的值。
有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入: ["2", "1", "+", "3", " * "]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
其实逆波兰表达式相当于是二叉树中的后序遍历。 大家可以把运算符作为中间节点，按照后序遍历的规则画出一个二叉树。
逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。
我们习惯看到的表达式都是中缀表达式，因为符合我们的习惯，但是中缀表达式对于计算机来说就不是很友好了。
例如：4 + 13 / 5，这就是中缀表达式，计算机从左到右去扫描的话，扫到13，还要判断13后面是什么运算法，还要比较一下优先级，然后13还和后面的5做运算，做完运算之后，还要向前回退到 4 的位置，继续做加法，你说麻不麻烦！
那么将中缀表达式，转化为后缀表达式之后：["4", "13", "5", "/", "+"] ，就不一样了，计算机可以利用栈里顺序处理，不需要考虑优先级了。也不用回退了， 所以后缀表达式对计算机来说是非常友好的。
可以说本题不仅仅是一道好题，也展现出计算机的思考方式。
在1970年代和1980年代，惠普在其所有台式和手持式计算器中都使用了RPN（后缀表达式），直到2020年代仍在某些模型中使用了RPN。
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> calcStack = new ArrayDeque<Integer>();
for(int i = 0; i < tokens.length; i++){
String token = tokens[i];
if(!isOperator(token)){
calcStack.push(Integer.parseInt(token));
}else{
//注意运算数顺序，先弹出的是第二个运算数
int operand2 = calcStack.pop();
int operand1 = calcStack.pop();
switch(token) {
case "+":
calcStack.push(operand1 + operand2);
break;
case "-":
calcStack.push(operand1 - operand2);
break;
case "*":
calcStack.push(operand1 * operand2);
break;
case "/":
calcStack.push(operand1 / operand2);
break;
default:
}
}
}
return calcStack.pop();
}
private boolean isOperator(String c){
return (c.equals("+") || c.equals("-") || c.equals("*") || c.equals("/"));
}
}
> 实现时的几点注意：
1. 注意出栈时的运算顺序，先出栈的是第二个运算数，后出栈的是第一个运算数；
2. 注意String比较相等时用equal(); 如果用 == 比较的是reference,不是value
时间复杂度： O（n）
空间复杂度： O(n) 使用栈存储计算过程中的数，栈内元素个数不会超过逆波兰表达式的长度。
239. 滑动窗口最大值 hard
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
这是使用单调队列的经典题目。
暴力解法思路：
遍历一遍的过程中每次从窗口中在找到最大的数值，这样很明显时间复杂度是O(n × k)。
进阶：
你能在线性时间复杂度内解决此题吗？
单调栈(Monotonic Stack) - 栈中元素按递增或者递减顺序排列
单调栈最大好处就是时间复杂度是线性的
优先队列：
A PriorityQueue is used when the objects are supposed to be processed based on the priority.
优先队列在普通队列的基础上给每个元素增加了优先级，这样每次出队的元素不再是队首的元素，而是队列中优先级最高的元素，而具体的优先级可以自行定义，典型的就是按元素从大到小或从小到大的顺序定义优先级。
优先队列一般采用二叉堆来实现
单调队列：
和单调栈类似，单调队列也必须维护其内元素的有序性。如：
若要入队一个元素11，就会打破现在的单调性，此时只能将大于11的元素全部出队。但仔细观察就会发现，如果这是一个普通队列，无论怎样出队入队，都不可能实现在保留比11小的元素基础上去除比11大的元素，因为普通队列只能在队首出队、队尾入队，而现在很明显我们需要在队尾出队。所以这里告诉我们，单调队列是使用双端队列实现的。
对于本题，需要一个满足以下操作的队列：
void poll() 用来抛出滑动窗口中移除元素的数值
void add(value) add滑动窗口添加元素的数值
int peek() 返回滑动窗口的最大值
问题是如何将队列排序使最大值始终处于头元素，同时又能按顺序移除元素呢？？？
其实队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队里里的元素数值是由大到小的。
本题的单调队列可以设计如下：
- void poll(value) 如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
- void add(value) 如果add的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到add元素的数值小于等于队列入口元素的数值为止
- int peek() 保持1,2的操作，调用peek()就可以返回当前窗口的最大值。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 1) {
return nums;
}
int[] resArr = new int[nums.length - k + 1];
int num = 0;
//自定义队列
MyQueue myQueue = new MyQueue();
for(int i = 0; i < k; i++){
myQueue.add(nums[i]);
}
resArr[num++] = myQueue.peek();
for(int i = k; i < nums.length; i++){
//滑动窗口移除最前面的元素
myQueue.poll(nums[i - k]);
//滑动窗口加入最后面的元素
myQueue.add(nums[i]);
//记录最大值
resArr[num++] = myQueue.peek();
}
return resArr;
}
}
class MyQueue{
Deque<Integer> deque = new LinkedList<Integer>();
//如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
void poll(int val){
if(!deque.isEmpty() && deque.peek() == val) {
deque.poll(); //deque.removeFirst();
}
}
//添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出
//保证队列元素单调递减
//比如此时队列元素3,1，2将要入队，比1大，所以1弹出，此时队列：3,2
void add(int val){
while(!deque.isEmpty() && deque.getLast() < val ) {
deque.removeLast();
}
deque.add(val);
}
//队列队顶元素始终为最大值
int peek(){
return deque.peekFirst();
}
}
使用单调队列的时间复杂度是 O(n). nums 中的每个元素最多也就被 push_back 和 pop_back 各一次，没有任何多余操作，所以整体的复杂度还是 O(n)。
空间复杂度 O(k) 因为使用了一个辅助队列
方法二：利用双端队列Deque手动实现单调队列
Deque 中存储的是元素下标
//利用双端队列手动实现单调队列
/**
* 用一个单调队列来存储对应的下标，每当窗口滑动的时候，直接取队列的头部指针对应的值放入结果集即可
* 单调队列类似 （tail -->） 3 --> 2 --> 1 --> 0 (--> head) (右边为头结点，元素存的是下标)
*/
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
ArrayDeque<Integer> deque = new ArrayDeque<>();
int n = nums.length;
int[] res = new int[n - k + 1];
int idx = 0;
for(int i = 0; i < n; i++) {
// 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点
// 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
while(!deque.isEmpty() && deque.peek() < i - k + 1){
deque.poll();
}
// 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出
while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
deque.offer(i);
// 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
if(i >= k - 1){
res[idx++] = nums[deque.peek()];
}
}
return res;
}
}
347. 前 K 个高频元素
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
统计元素出现的频率，这一类的问题可以使用map来进行统计。
然后是对频率进行排序，这里我们可以使用一种 容器适配器就是优先级队列。
优先级队列（priority queue），就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。
优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢？
缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。
什么是堆呢？
堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。
class Solution {
public int[] topKFrequent(int[] nums, int k) {
int[] res = new int[k];
//解法1：基于大顶堆实现
//map记录出现频率，key为数组元素值,val为对应出现次数
Map<Integer, Integer> freqMap = new HashMap<Integer, Integer>();
for(int i = 0; i < nums.length; i++){
freqMap.merge(nums[i],1, Integer::sum);
}
//在优先队列中存储二元组(num,cnt),cnt表示元素值num在数组中的出现次数
//出现次数按从队头到队尾的顺序是从大到小排,出现次数最多的在队头(相当于大顶堆)
//PriorityQueue(Comparator<? super E> comparator)
PriorityQueue<int[]> pq = new PriorityQueue<int[]>((int[] pair1, int[] pair2) -> pair2[1] - pair1[1]);
for(Map.Entry<Integer,Integer> entry : freqMap.entrySet()){
pq.add(new int[]{entry.getKey(), entry.getValue()});
}
//依次从队头弹出k个,就是出现频率前k高的元素
for(int i = 0; i < k; i++){
res[i] = pq.poll()[0];
}
return res;
}
}
时间复杂度：O(nlogk)，遍历一遍数组统计元素的频率，这一系列操作的时间复杂度是 O(n)；接着，遍历用于存储元素频率的 map，如果元素的频率大于最小堆中顶部的元素，则将顶部的元素删除并将该元素加入堆中，这里维护堆的数目是 k，所以这一系列操作的时间复杂度是 O(nlogk) 的
基于小顶堆实现：
class Solution {
public int[] topKFrequent(int[] nums, int k) {
int[] res = new int[k];
//解法1：基于小顶堆实现
//map记录出现频率，key为数组元素值,val为对应出现次数
Map<Integer, Integer> freqMap = new HashMap<Integer, Integer>();
for(int i = 0; i < nums.length; i++){
//freqMap.merge(nums[i],1, Integer::sum);
freqMap.put(nums[i], freqMap.getOrDefault(nums[i],0) + 1);
}
//在优先队列中存储二元组(num,cnt),cnt表示元素值num在数组中的出现次数
//出现次数按从队头到队尾的顺序是从小到大,出现次数最少的在队头
//PriorityQueue(Comparator<? super E> comparator)
PriorityQueue<int[]> pq = new PriorityQueue<int[]>((pair1, pair2) -> pair1[1] - pair2[1]);
for(Map.Entry<Integer,Integer> entry : freqMap.entrySet()){
if(pq.size() < k){
pq.add(new int[]{entry.getKey(), entry.getValue()});
}else{
//当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)
//弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了
if(pq.peek()[1] < entry.getValue()){
pq.poll();
pq.add(new int[]{entry.getKey(), entry.getValue()});
}
}
}
for(int i = 0; i < k; i++){
res[i] = pq.poll()[0];
}
return res;
}
}
总结
栈里面的元素在内存中是连续分布的么？
这个问题有两个陷阱：
陷阱1：栈是容器适配器，底层容器使用不同的容器，导致栈内数据在内存中是不是连续分布。
陷阱2：缺省情况下，默认底层容器是deque，那么deque的在内存中的数据分布是什么样的呢？ 答案是：不连续的
递归的实现是栈：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。
