代码随想录算法训练营day 10-11：栈与队列，滑动窗口最大值，大小顶堆

用**栈**解决“匹配，消除，计算”问题

这类题的共同点：当前状态，依赖于最近一次未处理完的状态

对应习题：20. 有效的括号，1047. 删除字符串中的所有相邻重复项，150. 逆波兰表达式求值

做这些题会有一种“消消乐”的感觉，当前元素和上一个元素如果满足某种条件，进行一次操作，循环往复，这种情况是栈的天然适配场景

用**设计结构**解决“区间，频率”问题

这类题的共同点：为“查询目标”定制数据结构

对应习题：239.滑动窗口最大值，347.前k个高频元素

这些题就体现了：队列比起一个“容器”，它更像一种“行为约束”，栈同理。

239.滑动窗口最大值

要做这题，首先要注意到一个关键事实：“当窗口内的某个元素的后续元素比它自身大时，这个元素就不可能成为最大值了”。

为什么呢？举个例子：假设窗口内元素为[ 4，3，2，5 ]，窗口内的 4 ，3 ，2如果想成为最大值，需要等待比他们大的5滑出窗口，然而事实是，窗口向右滑动，4,3,2绝对比5先滑出窗口，所以在5进入窗口的那一刻，前三个元素已经不可能成为最大值了

所以我们要做的是，维护一个非单增队列，储存可能成为当前窗口最大值的候选，队头是当前窗口最大值，窗口滑动后，若队头滑出窗口，队头出队即可，需要元素入队时，删除所有比该元素大的队尾元素，然后该元素进入队尾，由此来维护队列的“非单调递增性”，明白了这个单调队列的思想，剩下的操作就比较简单了。

347.前k个高频元素

这题可以用“堆”来做，即优先队列，堆的顶部永远是最大或最小值，所以，先用HashMap统计一遍频率，再把元素塞入堆，用大顶堆还是小顶堆呢？其实用小顶堆会更好，如果用大顶堆，那该堆需要维护所有的元素频率，再弹出顶部元素k次，得到topk，内存和时间都会有浪费。其实用容量为k的小顶堆即可，频率比堆顶大的元素就入堆，堆容量大于k就弹出顶部的最小频率，最后得到topk