文章目录
- 优先级队列介绍
- 与优先级队列有关的习题
- [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 accessPriorityQueue的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[]>(){
@Override
public 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];
} });