class KthLargest {
final PriorityQueue<Integer> minHeap;
final int k;
public KthLargest(int k, int[] nums) {
this.k = k;
this.minHeap = new PriorityQueue<>(k);
for (int i = 0; i < nums.length; i ++) {
add(nums[i]);
}
}
public int add(int val) {
if (minHeap.size() < k) {
minHeap.offer(val);
} else if (minHeap.peek() < val) {
minHeap.poll();
minHeap.offer(val);
}
return minHeap.peek();
}
}
// 本题属于困难题目，难点有两点，一是选择合适的数据结构作为滑动窗口，二是如何淘汰过期和不符合要求的数据
// 数据结构选用双端队列
// 过期元素从队列头淘汰
// 不符合要求的数据从队尾淘汰
// 注意：当新元素加入时，原窗口中比新元素小的数据，一定不会成为最大值，所以可以全部淘汰掉
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length <= 0) {
return new int[0];
}
Deque<Integer> windows = new ArrayDeque<>();
int[] result = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i ++) {
// 清除过期元素
if (i >= k && windows.peekFirst() <= i - k) {
windows.pollFirst();
}
// 清除比新插入数小的元素
while (!windows.isEmpty() && nums[i] >= nums[windows.getLast()]) {
windows.pollLast();
}
// 将最新一位加入
windows.add(i);
if (i >= k-1) {
result[i - k + 1] = nums[windows.peekFirst()];
}
}
return result;
}
