文章目錄

• 優先級隊列介紹
• 與優先級隊列有關的習題
• • [179. 最大數]
  • [918. 環形子數組的最大和]
  • [1094. 拼車]
  • [264. 丑數 II]
  • 前k個出現頻率最高的數字
  • 用優先級隊列合并k個有序鏈表
  • 滑動窗口的最大值
• 其他：對二維數組自定義排序

---

優先級隊列介紹

優先隊列一般基于二叉堆實現，二叉堆：
堆的根節點的優先級最大（即最大或最小）
父節點的優先級必定大于子節點，兄弟節點的優先級不確定誰大誰小

PriorityQueue：

PriorityQueue是基于二叉堆原理的優先隊列，隊列用動態數組實現。
它是非阻塞的、非線程安全的；
PriorityQueue內部維護了幾個重要屬性：

transient Object[] queue; // non-private to simplify nested class access/*** The number of elements in the priority queue.*/private int size = 0;//比較器private final Comparator<? super E> comparator;//被修改的次數transient int modCount = 0; // non-private to simplify nested class access

PriorityQueue的peek()和element()操作是常數時間，add()、offer()、 無參數的remove()以及poll()方法的時間復雜度都是log(N)。

PriorityBlockingQueue和PriorityQueue的實現基本一致區別就是在于加鎖了，并發出了非空信號喚醒阻塞的獲取線程。

1、jdk內置的優先隊列PriorityQueue內部使用一個堆維護數據，每當有數據add進來或者poll出去的時候會對堆做從下往上的調整和從上往下的調整。

2、PriorityQueue不是一個線程安全的類，如果要在多線程環境下使用，可以使用 PriorityBlockingQueue 這個優先阻塞隊列。其中add、poll、remove方法都使用 ReentrantLock 鎖來保持同步，take() 方法中如果元素為空，則會一直保持阻塞。

與優先級隊列有關的習題

[179. 最大數]

(https://leetcode-cn.com/problems/largest-number/)
給定一組非負整數 nums，重新排列每個數的順序（每個數不可拆分）使之組成一個最大的整數。

**注意：**輸出結果可能非常大，所以你需要返回一個字符串而不是整數。

示例 1：

輸入：nums = [10,2] 輸出："210"

示例 2：

輸入：nums = [3,30,34,5,9] 輸出："9534330" public String largestNumber(int[] nums) { PriorityQueue<String>queue = new PriorityQueue<>((x,y)->(y+x).compareTo(x+y)); for(int i:nums) queue.offer(String.valueOf(i)); String ans=""; while(queue.size()>0) { ans+=queue.poll(); } if(ans.charAt(0)=='0') return"0"; return ans;}

[918. 環形子數組的最大和]

(https://leetcode-cn.com/problems/maximum-sum-circular-subarray/)
首先關于一般數組的最大和：

int maxSubArray(vector<int>& nums) {int pre = 0; int sum = nums[0]; for(const auto &i: nums){pre = max(pre+i,i);sum = max(pre,sum); } return sum;}

然后環形數組最大和的關鍵是知道最大和是怎么產生的，其實有兩種情況，一個是最大和是數組中間的數字之和（從第0索引到第length-1個索引之間某幾個數之和），另一個是由兩端的產生，（即包含0和length-1索引，但中間有的元素不包含），第二種情況是有負數的情況，如[8,-1,-1,1],這樣需要用所有元素之和減去最小子數組來求，有一種特殊情況，如果全為負數這時候所有元素之和減去最小子數組為0，這個環形數組的最大和應該是元素中最大的那個數，概況：

對于環形數組，分兩種情況。
(1)答案在數組中間，就是最大子序和。例如[1,-2,3,-2]；
(2)答案在數組兩邊，例如[5,-3,5]最大的子序和就等于數組的總和SUM-最小的子序和。(一種特殊情況是數組全為負數，也就是SUM-最小子序和==0，最大子序和等于數組中最大的那個)。

public int maxSubarraySumCircular(int[] nums) { int premax = 0,premin = 0,maxval = nums[0],minval = nums[0],sum=0; for(int i = 0;i < nums.length;i++) {premax = Math.max(premax+nums[i],nums[i]);maxval = Math.max(maxval,premax);premin = Math.min(premin+nums[i],nums[i]);minval = Math.min(minval,premin);sum+=nums[i]; } return Math.max(maxval,sum-minval ==0?maxval:sum-minval);}

[1094. 拼車]

(https://leetcode-cn.com/problems/car-pooling/)
難度中等146

假設你是一位順風車司機，車上最初有 capacity 個空座位可以用來載客。由于道路的限制，車 只能 向一個方向行駛（也就是說，不允許掉頭或改變方向，你可以將其想象為一個向量）。

這兒有一份乘客行程計劃表 trips[][]，其中 trips[i] = [num_passengers, start_location, end_location] 包含了第 i 組乘客的行程信息：

• 必須接送的乘客數量；
• 乘客的上車地點；
• 以及乘客的下車地點。

這些給出的地點位置是從你的 初始 出發位置向前行駛到這些地點所需的距離（它們一定在你的行駛方向上）。

請你根據給出的行程計劃表和車子的座位數，來判斷你的車是否可以順利完成接送所有乘客的任務（當且僅當你可以在所有給定的行程中接送所有乘客時，返回 true，否則請返回 false）。

示例 1：

輸入：trips = [[2,1,5],[3,3,7]], capacity = 4
輸出：false
示例 2：

輸入：trips = [[2,1,5],[3,3,7]], capacity = 5
輸出：true
示例 3：

輸入：trips = [[2,1,5],[3,5,7]], capacity = 3
輸出：true

---

首先按分別按上車地點和下車地點維護兩個小頂堆。每次比較堆頂元素，并維護當前容量，若下車地點更小（或相等），先下車（當前容量增加），否則上車（當前容量減小），上車時要判斷當前容量是否變成負值，若變成負值應直接返回false。
注意，因為最后一個下車地點一定大于最后一個上車地點，因此按上車地點維護的小頂堆一定先變為空。

public boolean carPooling(int[][] trips, int capacity) { PriorityQueue<int[]>up = new PriorityQueue<>((a,b)->a[1]-b[1]);//按上車地點進行排序 PriorityQueue<int[]>down = new PriorityQueue<>((a,b)->a[2]-b[2]); for(int i = 0;i<trips.length;i++) {up.offer(trips[i]);down.offer(trips[i]); } while(!up.isEmpty()) {int start = up.peek()[1];int end = down.peek()[2];if(end<=start){int[] temp=down.poll();//下車，容量增加capacity+=temp[0];}else{int[] temp = up.poll();capacity-=temp[0];}if(capacity<0) return false; } return true;}

[264. 丑數 II]

(https://leetcode-cn.com/problems/ugly-number-ii/)
難度中等

給你一個整數 n ，請你找出并返回第 n 個 丑數 。

丑數 就是只包含質因數 2、3 和/或 5 的正整數。

示例 1：

輸入：n = 10 輸出：12 解釋：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 個丑數組成的序列。

示例 2：

輸入：n = 1 輸出：1 解釋：1 通常被視為丑數。

---

要得到從小到大的第 n個丑數，可以使用最小堆實現。

初始時堆為空。首先將最小的丑數 1加入堆。

每次取出堆頂元素 xx，則 xx 是堆中最小的丑數，由于 2x, 3x, 5x 也是丑數，因此將 2x, 3x, 5x 加入堆。

上述做法會導致堆中出現重復元素的情況。為了避免重復元素，可以使用哈希集合去重，避免相同元素多次加入堆。

在排除重復元素的情況下，第 n 次從最小堆中取出的元素即為第 n 個丑數。

public int nthUglyNumber(int n) { int[]ug=new int[]{2,3,5}; PriorityQueue<Long>queue = new PriorityQueue<>(); Set<Long>myset = new HashSet<>();//在添加元素的過程中可能出現非常大的數，因此要用long類型 queue.offer(1L);//1是丑數 myset.add(1L);int ans=1; for(int i = 0;i<n;i++) {long heap=queue.poll();ans = (int)heap;//強制轉化為int類型for(int j = 0;j < ug.length;j++){long temp = heap*ug[j];if(myset.add(temp))//用于去重，如果hashset可以添加成功則證明這個元素沒有出現過，可以添加到堆中queue.offer(temp);} } return ans;}

前k個出現頻率最高的數字

public int[] topKFrequent(int[] nums, int k) {Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();for (int num : nums) {occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);}// int[] 的第一個元素代表數組的值，第二個元素代表了該值出現的次數PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {public int compare(int[] m, int[] n) {return m[1] - n[1];//這一步比較不能寫反，否則結果是錯的}});for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {int num = entry.getKey(), count = entry.getValue();if (queue.size() == k) {if (queue.peek()[1] < count) {queue.poll();queue.offer(new int[]{num, count});}} else {queue.offer(new int[]{num, count});}}int[] ret = new int[k];for (int i = 0; i < k; ++i) {ret[i] = queue.poll()[0];}return ret;} }

用優先級隊列合并k個有序鏈表

class Status implements Comparable<Status> {int val;ListNode ptr;public Status(int val,ListNode ptr){this.val=val;this.ptr=ptr;}public int compareTo(Status s2){ return ptr.val-s2.val;}}PriorityQueue<Status>queue=new PriorityQueue<Status>();public ListNode mergeKLists(ListNode[] lists) { for(ListNode node:lists) if (node != null) { queue.offer(new Status(node.val,node)); } ListNode head=new ListNode(0); ListNode tail=head; while(!queue.isEmpty()) {Status f=queue.poll();tail.next=f.ptr;tail=f.ptr;if(f.ptr.next!=null)queue.offer(new Status(f.ptr.next.val,f.ptr.next));//這一步比較巧妙，沒有直接展開上面的所有鏈表結點，而是先將鏈表數組中的元素按照第一個結點的大小加入優先級隊列，后再對每一個結點中尋找下一個結點加入隊列 } return head.next;}

滑動窗口的最大值

給你一個整數數組 nums，有一個大小為 k 的滑動窗口從數組的最左側移動到數組的最右側。你只可以看到在滑動窗口內的 k 個數字。滑動窗口每次只向右移動一位。

返回 滑動窗口中的最大值 。

示例 1：

輸入：nums = [1,3,-1,-3,5,3,6,7], k = 3
輸出：[3,3,5,5,6,7]
解釋：
滑動窗口的位置 最大值

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

---

由于出現了最大值，用優先級隊列可以維護每次窗口的最大值，其中用數組下標用來排除窗口之外的元素

public int[] maxSlidingWindow(int[] nums, int k) { int[]ans = new int[nums.length+1-k]; PriorityQueue<int[]>queue = new PriorityQueue<int[]>(new Comparator<int[]>(){@Overridepublic int compare(int[]a1,int[]a2){return a1[0]==a2[0]?a2[1]-a1[1]:a2[0]-a1[0];} }); for(int i = 0;i <k;i++) queue.offer(new int[]{nums[i],i}); int index = 0; ans[0]= queue.peek()[0]; for(int i = k;i<nums.length;i++) {queue.offer(new int[]{nums[i],i});while(queue.peek()[1] <= i-k)//注意這里是while循環不是if判斷queue.poll();ans[i-k+1] = queue.peek()[0];} return ans;}

其他：對二維數組自定義排序

Arrays.sort(intervals,new Comparator<int[]>() { @Override public int compare(int[]a,int[]b) {return a[0]==b[0]?b[1]-a[1]:a[0]-b[0]; } });

總結

以上是生活随笔為你收集整理的优先级队列PriorityQueue在算法问题中的使用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。