239. 滑動(dòng)窗口最大值
題目鏈接：https://leetcode.cn/problems/sliding-window-maximum/
解答：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
本題為隊(duì)列的應(yīng)用。
每次窗口移動(dòng)的時(shí)候砂豌，調(diào)用que.pop(滑動(dòng)窗口中移除元素的數(shù)值)，que.push(滑動(dòng)窗口添加元素的數(shù)值)绳瘟，然后que.front()就返回我們要的最大值——我們需要自己實(shí)現(xiàn)這個(gè)隊(duì)列
然后再分析一下，隊(duì)列里的元素一定是要排序的而叼，而且要最大值放在出隊(duì)口身笤，要不然怎么知道最大值呢
隊(duì)列沒有必要維護(hù)窗口里的所有元素，只需要維護(hù)有可能成為窗口里最大值的元素就可以了葵陵，同時(shí)保證隊(duì)列里的元素?cái)?shù)值是由大到小的液荸。那么這個(gè)維護(hù)元素單調(diào)遞減的隊(duì)列就叫做單調(diào)隊(duì)列，即單調(diào)遞減或單調(diào)遞增的隊(duì)列脱篙。
設(shè)計(jì)單調(diào)隊(duì)列的時(shí)候娇钱，pop，和push操作要保持如下規(guī)則：
1. pop(value)：如果窗口移除的元素value等于單調(diào)隊(duì)列的出口元素绊困，那么隊(duì)列彈出元素文搂，否則不用任何操作
2. push(value)：如果push的元素value大于入口元素的數(shù)值，那么就將隊(duì)列入口的元素彈出秤朗，直到push元素的數(shù)值小于等于隊(duì)列入口元素的數(shù)值為止
保持如上規(guī)則煤蹭，每次窗口移動(dòng)的時(shí)候，只要問que.front()就可以返回當(dāng)前窗口的最大值取视。
347.前 K 個(gè)高頻元素
題目鏈接：https://leetcode.cn/problems/top-k-frequent-elements/
解答：https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html
題目?jī)?nèi)容：給定一個(gè)非空的整數(shù)數(shù)組硝皂，返回其中出現(xiàn)頻率前 k 高的元素。
條件：
1. 你可以假設(shè)給定的 k 總是合理的作谭，且 1 ≤ k ≤ 數(shù)組中不相同的元素的個(gè)數(shù)稽物。
2.?題目數(shù)據(jù)保證答案唯一，換句話說折欠，數(shù)組中前 k 個(gè)高頻元素的集合是唯一的贝或。
大頂堆和小頂堆：底層數(shù)據(jù)結(jié)構(gòu)是二叉樹
優(yōu)先級(jí)隊(duì)列的底層實(shí)現(xiàn)就是堆，可以使用優(yōu)先級(jí)隊(duì)列實(shí)現(xiàn)大頂堆和小頂堆锐秦。
Java 優(yōu)先級(jí)隊(duì)列介紹：https://blog.csdn.net/sheng0113/article/details/123140959
優(yōu)先級(jí)隊(duì)列可以保證每次取出來的元素都是隊(duì)列中的最小或最大的元素咪奖，即小頂堆和大頂堆（Java優(yōu)先級(jí)隊(duì)列默認(rèn)每次取出來的為最小元素）
PriorityQueue是Queen接口的一個(gè)實(shí)現(xiàn)類，而Queen接口是Collection接口的一個(gè)實(shí)現(xiàn)類农猬，因此其擁有Collection接口的基本操作（add，remove售淡，element）斤葱，此外，隊(duì)列還提供了其他的插入（offer）揖闸，移除（poll）和查詢（peek）的操作揍堕。
注意??：優(yōu)先級(jí)隊(duì)列中不可以存儲(chǔ)null
優(yōu)先級(jí)隊(duì)列默認(rèn)每次獲取隊(duì)列中最小的元素，也可以通過comparator比較器來自定義每次獲取為最小還是最大汤纸。
Java 優(yōu)先級(jí)隊(duì)列詳解：https://blog.csdn.net/m0_51013067/article/details/126521551
PriorityQueue <Integer> heap = new PriorityQueue<>( (n1,n2) -> n1-n2;? //這一句加不加結(jié)果是一樣的
如果改成n2-n1衩茸，就會(huì)變成大頂堆：
優(yōu)先隊(duì)列內(nèi)部是按照比較器返回的結(jié)果進(jìn)行處理的，一般認(rèn)為a,b兩個(gè)值贮泞，比較結(jié)果大于0就是a大于b楞慈，a下沉幔烛；等于0就是a等于b；小于0就是a小于b囊蓝，b下沉饿悬；現(xiàn)在我們知道當(dāng)比較n1,n2的時(shí)候，如果結(jié)果大于0(也就是默認(rèn)的n1-n2>0)聚霜，那么要把n1下沉(默認(rèn)的小根堆)狡恬，當(dāng)我們改成n2-n1的時(shí)候，結(jié)果大于0蝎宇，證明n2大于n1弟劲，但還是n1（值較小的元素）下沉，于是這個(gè)堆就成了大頂堆姥芥。
自定義comparator比較器：
就像TreeSet一樣兔乞，一個(gè)priority queue要么存儲(chǔ)的是實(shí)現(xiàn)了Comparable接口的元素，要么在構(gòu)造函數(shù)中傳入一個(gè)Comparator對(duì)象撇眯。
public class ListNode {
int val;
? ? ? ? ListNode next;
? ? ? ? ListNode() {}
? ? ? ? ListNode(int val) { this.val = val; }
? ? ? ? ListNode(int val, ListNode next) { this.val = val; this.next = next; }
? ? }
//自定義比較類报嵌，升序排列
? ? static Comparator<ListNode> cLNode = new Comparator<ListNode>() {
? ? ? ? public int compare(ListNode o1, ListNode o2) {
? ? ? ? ? ? ? ? return o1.val-o2.val;? ? ? ? }
? ? };
? ? public static void main(String[] args) {
? ? //自定義類的優(yōu)先隊(duì)列需要重寫比較類作為傳入?yún)?shù)
? ? ? ? Queue<ListNode> que = new PriorityQueue<>(cLNode);?
? ? ? ? //簡(jiǎn)單寫法
? ? ? ? // Queue<ListNode> que = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
? ? }
Comparable接口：
public interface Comparable<T> {
? ? public int compareTo (T o);
}
該接口只存在一個(gè)public int compareTo(T o);方法，該方法表示所在的對(duì)象和o對(duì)象進(jìn)行比較熊榛，返回值分三種：
1：?表示當(dāng)前對(duì)象大于o對(duì)象
0：?表示當(dāng)前對(duì)象等于o對(duì)象
-1：?表示當(dāng)前對(duì)象小于o對(duì)象
在優(yōu)先級(jí)隊(duì)列中或者具有比較特征的集合中存儲(chǔ)的對(duì)象需要實(shí)現(xiàn)Comparable接口锚国。
例子??：
需求：?在優(yōu)先級(jí)隊(duì)列中存儲(chǔ)對(duì)象學(xué)生，每個(gè)學(xué)生有id玄坦，name血筑，age三個(gè)屬性，并且使優(yōu)先級(jí)隊(duì)列每次按照學(xué)生的id從小到大取出煎楣。
Student類：?當(dāng)前類實(shí)現(xiàn)了Comparable接口豺总，即當(dāng)前類提供了默認(rèn)的比較方法。
public class Student implements Comparable{
? ? private int id;
? ? private String name;
? ? private int age;
? ? public Student(int id, String name, int age) {
? ? ? ? this.id = id;
? ? ? ? this.name = name;
? ? ? ? this.age = age;
? ? }
? ? @Override
? ? public int compareTo (Object o) {
? ? ? ? Student o1 = (Student)o;
? ? ? ? return this.id - o1.id;
? ? }
}
優(yōu)先隊(duì)列?pq?中的元素個(gè)數(shù)最多是?k择懂，所以一次?poll?或者?add?方法的時(shí)間復(fù)雜度是?O(logk)喻喳；所有的鏈表節(jié)點(diǎn)都會(huì)被加入和彈出?pq，所以算法整體的時(shí)間復(fù)雜度是?O(Nlogk)困曙，其中?k?是鏈表的條數(shù)表伦，N?是這些鏈表的節(jié)點(diǎn)總數(shù)。
棧與隊(duì)列總結(jié)：https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E6%80%BB%E7%BB%93.html
用隊(duì)列模擬棧 優(yōu)化版：
其實(shí)這道題目就是用一個(gè)隊(duì)列就夠了
思路：
一個(gè)隊(duì)列在模擬棧彈出元素的時(shí)候只要將隊(duì)列頭部的元素（除了最后一個(gè)元素外） 重新添加到隊(duì)列尾部慷丽，此時(shí)再去彈出元素就是棧的順序了
