239: 滑动窗口最大值
LeetCode 239(滑动窗口最大值)
import java.util.Deque;
import java.util.LinkedList;
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length - k + 1];
int index = 0;
Deque<Integer> queue = new LinkedList<>();
for (int i = 0; i < k; i++){
while(!queue.isEmpty() && queue.peekLast() < nums[i]){
queue.pollLast();
}
queue.offerLast(nums[i]);
}
res[index++] = queue.peekFirst();
for(int i = k; i < nums.length; i++){
//看要不要出栈
if(queue.peekFirst() == nums[i - k]){
queue.pollFirst();
}
//看要不要进栈
while(!queue.isEmpty() && queue.peekLast() < nums[i]){
queue.pollLast();
}
queue.offerLast(nums[i]);
res[index++] = queue.peekFirst();
}
return res;
}
}
347: 前K个高频元素
LeetCode 347(前K个高频元素)
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Set;
class Solution {
public int[] topKFrequent(int[] nums, int k) {
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(
(x,y) -> y[1] - x[1]
);
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int len = nums.length;
for (int i = 0; i < len; i++) {
map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
}
Set<Integer> keySet = map.keySet();
for(int i : keySet) {
queue.offer(new int[]{i,map.get(i)});
}
int[] res = new int[k];
for(int i = 0;i < k;i++){
res[i] = queue.poll()[0];
}
return res;
}
}