239. 婊戝姩绐楀彛鏈€澶у€?/p>
棰樼洰閾炬帴锛歨ttps://leetcode.cn/problems/sliding-window-maximum/
瑙ｇ瓟锛歨ttps://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
鏈涓洪槦鍒楃殑搴旂敤銆?/p>
姣忔绐楀彛绉诲姩鐨勬椂鍊欙紝璋冪敤que.pop(婊戝姩绐楀彛涓Щ闄ゅ厓绱犵殑鏁板€?锛宷ue.push(婊戝姩绐楀彛娣诲姞鍏冪礌鐨勬暟鍊?锛岀劧鍚巕ue.front()灏辫繑鍥炴垜浠鐨勬渶澶у€尖€斺€旀垜浠渶瑕佽嚜宸卞疄鐜拌繖涓槦鍒?/p>
鐒跺悗鍐嶅垎鏋愪竴涓嬶紝闃熷垪閲岀殑鍏冪礌涓€瀹氭槸瑕佹帓搴忕殑锛岃€屼笖瑕佹渶澶у€兼斁鍦ㄥ嚭闃熷彛锛岃涓嶇劧鎬庝箞鐭ラ亾鏈€澶у€煎憿
闃熷垪娌℃湁蹇呰缁存姢绐楀彛閲岀殑鎵€鏈夊厓绱狅紝鍙渶瑕佺淮鎶ゆ湁鍙兘鎴愪负绐楀彛閲屾渶澶у€肩殑鍏冪礌灏卞彲浠ヤ簡锛屽悓鏃朵繚璇侀槦鍒楅噷鐨勫厓绱犳暟鍊兼槸鐢卞ぇ鍒板皬鐨勩€傞偅涔堣繖涓淮鎶ゅ厓绱犲崟璋冮€掑噺鐨勯槦鍒楀氨鍙仛鍗曡皟闃熷垪锛屽嵆鍗曡皟閫掑噺鎴栧崟璋冮€掑鐨勯槦鍒椼€?/b>
璁捐鍗曡皟闃熷垪鐨勬椂鍊欙紝pop锛屽拰push鎿嶄綔瑕佷繚鎸佸涓嬭鍒欙細
1. pop(value)锛氬鏋滅獥鍙ｇЩ闄ょ殑鍏冪礌value绛変簬鍗曡皟闃熷垪鐨勫嚭鍙ｅ厓绱狅紝閭ｄ箞闃熷垪寮瑰嚭鍏冪礌锛屽惁鍒欎笉鐢ㄤ换浣曟搷浣?/p>
2. push(value)锛氬鏋減ush鐨勫厓绱爒alue澶т簬鍏ュ彛鍏冪礌鐨勬暟鍊硷紝閭ｄ箞灏卞皢闃熷垪鍏ュ彛鐨勫厓绱犲脊鍑猴紝鐩村埌push鍏冪礌鐨勬暟鍊煎皬浜庣瓑浜庨槦鍒楀叆鍙ｅ厓绱犵殑鏁板€间负姝?/p>
淇濇寔濡備笂瑙勫垯锛屾瘡娆＄獥鍙ｇЩ鍔ㄧ殑鏃跺€欙紝鍙闂畄ue.front()灏卞彲浠ヨ繑鍥炲綋鍓嶇獥鍙ｇ殑鏈€澶у€笺€?/p>
347.鍓?K 涓珮棰戝厓绱?/p>
棰樼洰閾炬帴锛歨ttps://leetcode.cn/problems/top-k-frequent-elements/
瑙ｇ瓟锛歨ttps://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html
棰樼洰鍐呭锛氱粰瀹氫竴涓潪绌虹殑鏁存暟鏁扮粍锛岃繑鍥炲叾涓嚭鐜伴鐜囧墠 k 楂樼殑鍏冪礌銆?/p>
鏉′欢锛?/p>
1. 浣犲彲浠ュ亣璁剧粰瀹氱殑 k 鎬绘槸鍚堢悊鐨勶紝涓?1 鈮?k 鈮?鏁扮粍涓笉鐩稿悓鐨勫厓绱犵殑涓暟銆?/p>
2.聽棰樼洰鏁版嵁淇濊瘉绛旀鍞竴锛屾崲鍙ヨ瘽璇达紝鏁扮粍涓墠 k 涓珮棰戝厓绱犵殑闆嗗悎鏄敮涓€鐨勩€?/p>
澶ч《鍫嗗拰灏忛《鍫嗭細搴曞眰鏁版嵁缁撴瀯鏄簩鍙夋爲
浼樺厛绾ч槦鍒楃殑搴曞眰瀹炵幇灏辨槸鍫嗭紝鍙互浣跨敤浼樺厛绾ч槦鍒楀疄鐜板ぇ椤跺爢鍜屽皬椤跺爢銆?/p>
Java 浼樺厛绾ч槦鍒椾粙缁嶏細https://blog.csdn.net/sheng0113/article/details/123140959
浼樺厛绾ч槦鍒楀彲浠ヤ繚璇佹瘡娆″彇鍑烘潵鐨勫厓绱犻兘鏄槦鍒椾腑鐨?b>鏈€灏?/b>鎴?b>鏈€澶?/b>鐨勫厓绱狅紝鍗冲皬椤跺爢鍜屽ぇ椤跺爢锛圝ava浼樺厛绾ч槦鍒楅粯璁ゆ瘡娆″彇鍑烘潵鐨勪负鏈€灏忓厓绱狅級
PriorityQueue鏄疩ueen鎺ュ彛鐨勪竴涓疄鐜扮被锛岃€孮ueen鎺ュ彛鏄疌ollection鎺ュ彛鐨勪竴涓疄鐜扮被锛屽洜姝ゅ叾鎷ユ湁Collection鎺ュ彛鐨勫熀鏈搷浣滐紙add锛宺emove锛宔lement锛夛紝姝ゅ锛岄槦鍒楄繕鎻愪緵浜嗗叾浠栫殑鎻掑叆锛坥ffer锛?/b>锛?b>绉婚櫎锛坧oll锛?/b>鍜?b>鏌ヨ锛坧eek锛?/b>鐨勬搷浣溿€?/p>
娉ㄦ剰鈿狅笍锛氫紭鍏堢骇闃熷垪涓笉鍙互瀛樺偍null
浼樺厛绾ч槦鍒楅粯璁ゆ瘡娆¤幏鍙栭槦鍒椾腑鏈€灏忕殑鍏冪礌锛屼篃鍙互閫氳繃comparator姣旇緝鍣?/b>鏉ヨ嚜瀹氫箟姣忔鑾峰彇涓烘渶灏忚繕鏄渶澶с€?/p>
Java 浼樺厛绾ч槦鍒楄瑙ｏ細https://blog.csdn.net/m0_51013067/article/details/126521551
PriorityQueue <Integer> heap = new PriorityQueue<>( (n1,n2) -> n1-n2;聽 //杩欎竴鍙ュ姞涓嶅姞缁撴灉鏄竴鏍风殑
濡傛灉鏀规垚n2-n1锛屽氨浼氬彉鎴愬ぇ椤跺爢锛?/p>
浼樺厛闃熷垪鍐呴儴鏄寜鐓ф瘮杈冨櫒杩斿洖鐨勭粨鏋滆繘琛屽鐞嗙殑锛屼竴鑸涓篴,b涓や釜鍊硷紝姣旇緝缁撴灉澶т簬0灏辨槸a澶т簬b锛宎涓嬫矇锛涚瓑浜?灏辨槸a绛変簬b锛涘皬浜?灏辨槸a灏忎簬b锛宐涓嬫矇锛涚幇鍦ㄦ垜浠煡閬撳綋姣旇緝n1,n2鐨勬椂鍊欙紝濡傛灉缁撴灉澶т簬0(涔熷氨鏄粯璁ょ殑n1-n2>0)锛岄偅涔堣鎶妌1涓嬫矇(榛樿鐨勫皬鏍瑰爢)锛屽綋鎴戜滑鏀规垚n2-n1鐨勬椂鍊欙紝缁撴灉澶т簬0锛岃瘉鏄巒2澶т簬n1锛屼絾杩樻槸n1锛堝€艰緝灏忕殑鍏冪礌锛変笅娌夛紝浜庢槸杩欎釜鍫嗗氨鎴愪簡澶ч《鍫嗐€?/p>
鑷畾涔塩omparator姣旇緝鍣細
灏卞儚TreeSet涓€鏍凤紝涓€涓猵riority queue瑕佷箞瀛樺偍鐨勬槸瀹炵幇浜咰omparable鎺ュ彛鐨勫厓绱狅紝瑕佷箞鍦ㄦ瀯閫犲嚱鏁颁腑浼犲叆涓€涓狢omparator瀵硅薄銆?/p>
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; }
聽 聽 }
//鑷畾涔夋瘮杈冪被锛屽崌搴忔帓鍒?/p>
聽 聽 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) {
聽 聽 //鑷畾涔夌被鐨勪紭鍏堥槦鍒楅渶瑕侀噸鍐欐瘮杈冪被浣滀负浼犲叆鍙傛暟
聽 聽 聽 聽 Queue<ListNode> que = new PriorityQueue<>(cLNode);聽
聽 聽 聽 聽 //绠€鍗曞啓娉?/p>
聽 聽 聽 聽 // Queue<ListNode> que = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
聽 聽 }
Comparable鎺ュ彛锛?/b>
public interface Comparable<T> {
聽 聽 public int compareTo (T o);
}
璇ユ帴鍙ｅ彧瀛樺湪涓€涓猵ublic int compareTo(T o);鏂规硶锛岃鏂规硶琛ㄧず鎵€鍦ㄧ殑瀵硅薄鍜宱瀵硅薄杩涜姣旇緝锛岃繑鍥炲€煎垎涓夌锛?/p>
1锛?/b>聽琛ㄧず褰撳墠瀵硅薄澶т簬o瀵硅薄
0锛?/b>聽琛ㄧず褰撳墠瀵硅薄绛変簬o瀵硅薄
-1锛?/b>聽琛ㄧず褰撳墠瀵硅薄灏忎簬o瀵硅薄
鍦ㄤ紭鍏堢骇闃熷垪涓垨鑰呭叿鏈夋瘮杈冪壒寰佺殑闆嗗悎涓瓨鍌ㄧ殑瀵硅薄闇€瑕佸疄鐜癈omparable鎺ュ彛銆?/p>
渚嬪瓙馃尠锛?/b>
闇€姹傦細聽鍦ㄤ紭鍏堢骇闃熷垪涓瓨鍌ㄥ璞″鐢燂紝姣忎釜瀛︾敓鏈?b>id锛?b>name锛?b>age涓変釜灞炴€э紝骞朵笖浣夸紭鍏堢骇闃熷垪姣忔鎸夌収瀛︾敓鐨刬d浠庡皬鍒板ぇ鍙栧嚭銆?/p>
Student绫伙細聽褰撳墠绫诲疄鐜颁簡Comparable鎺ュ彛锛屽嵆褰撳墠绫绘彁渚涗簡榛樿鐨勬瘮杈冩柟娉曘€?/p>
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;
聽 聽 }
}
浼樺厛闃熷垪聽pq聽涓殑鍏冪礌涓暟鏈€澶氭槸聽k锛屾墍浠ヤ竴娆÷爌oll聽鎴栬€吢燼dd聽鏂规硶鐨勬椂闂村鏉傚害鏄燨(logk)锛涙墍鏈夌殑閾捐〃鑺傜偣閮戒細琚姞鍏ュ拰寮瑰嚭聽pq锛?b>鎵€浠ョ畻娉曟暣浣撶殑鏃堕棿澶嶆潅搴︽槸聽O(Nlogk)锛屽叾涓爇聽鏄摼琛ㄧ殑鏉℃暟锛孨聽鏄繖浜涢摼琛ㄧ殑鑺傜偣鎬绘暟銆?/p>
鏍堜笌闃熷垪鎬荤粨锛歨ttps://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E6%80%BB%E7%BB%93.html
鐢ㄩ槦鍒楁ā鎷熸爤 浼樺寲鐗堬細
鍏跺疄杩欓亾棰樼洰灏辨槸鐢ㄤ竴涓槦鍒楀氨澶熶簡
鎬濊矾锛?/p>
涓€涓槦鍒楀湪妯℃嫙鏍堝脊鍑哄厓绱犵殑鏃跺€欏彧瑕佸皢闃熷垪澶撮儴鐨勫厓绱狅紙闄や簡鏈€鍚庝竴涓厓绱犲锛?閲嶆柊娣诲姞鍒伴槦鍒楀熬閮紝姝ゆ椂鍐嶅幓寮瑰嚭鍏冪礌灏辨槸鏍堢殑椤哄簭浜?/b>