优先队列
优先队列，也称为栈，它可以在保证队列的结构下，对队列的内部元素进行排序，可以按照某个值、从大、从小排序，由具体的Comparator决定。
使用优先队列的情况，一般存在于，需要集合中的最值，而这个集合又在更新的情况。同样的，优先队列常常不会专门成为一道题目，而是与其它算法搭配使用，优先队列可以作为一种算法小技巧。
一、最后一块石头的重量（简单）
class Solution {
public int lastStoneWeight(int[] stones) {
Queue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
@Override
// 重量从大到小
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
for (int i = 0; i < stones.length; i++) {
pq.offer(stones[i]);
}
while (!pq.isEmpty()) {
int a = pq.poll();
if (pq.isEmpty()) {
return a;
}
int b = pq.poll();
if (a == b) {
continue;
} else {
// 剩余石头再入队
pq.offer(Math.abs(a - b));
}
}
return 0;
}
}
二、数组中两元素的最大乘积（简单）
class Solution {
class node {
int index;
int val;
node(){};
node(int index, int val) {
this.index = index;
this.val = val;
}
}
public int maxProduct(int[] nums) {
Queue<node> pq = new PriorityQueue<>(new Comparator<node>() {
// 值从大到小排
@Override
public int compare(node o1, node o2) {
return o2.val - o1.val;
}
});
for (int i = 0; i < nums.length; i++) {
pq.offer(new node(i, nums[i] - 1));
}
return pq.poll().val * pq.poll().val;
}
}
三、根据字符出现频率排序（中等）
直接用优先队列就完事了，注意记录答案使用StringBuilder（SB）
class Solution {
class node {
char c;
int cnt;
node() {};
node(char c, int cnt) {
this.c = c;
this.cnt = cnt;
}
}
public String frequencySort(String s) {
int[] cnt = new int[200];
for (char tmp : s.toCharArray()) {
// 记录每个字符出现的次数
cnt[tmp]++;
}
Queue<node> pq = new PriorityQueue<>(new Comparator<node>() {
// 出现频率从高到低
@Override
public int compare(node o1, node o2) {
return o2.cnt - o1.cnt;
}
});
for (int i = 0; i < 200; i++) {
if (cnt[i] == 0) continue;
pq.offer(new node((char) (i), cnt[i]));
}
StringBuilder ans = new StringBuilder();
while (!pq.isEmpty()) {
node tmp = pq.poll();
char c = tmp.c;
int count = tmp.cnt;
while (count != 0) {
ans.append(c);
count--;
}
}
return ans.toString();
}
}
四、找到和最大的长度为k的子序列（简单）
class Solution {
class node {
int index;
int val;
node(){};
node(int index, int val) {
this.index = index;
this.val = val;
}
}
public int[] maxSubsequence(int[] nums, int k) {
Queue<node> pq = new PriorityQueue<node>(new Comparator<node>() {
@Override
public int compare(node o1, node o2) {
return o2.val - o1.val;
}
});
for (int i = 0; i < nums.length; i++) {
pq.offer(new node(i, nums[i]));
}
node[] tmp = new node[k];
int index = 0;
while (!pq.isEmpty() && index < k) {
tmp[index++] = pq.poll();
}
Arrays.sort(tmp, new Comparator<node>() {
// 再对答案按照下标从小到大排序
@Override
public int compare(node o1, node o2) {
return o1.index - o2.index;
}
});
int[] ans = new int[k];
for (int i = 0; i < k; i++) {
ans[i] = tmp[i].val;
}
return ans;
}
}
难点在于题目中的：不改变元素的顺序，存储每个元素的下标和value，先按照元素value的大小存入优先队列，选出最大的K个元素后，再对它们的下标排序，保证它们的原始顺序。