这道题一看题目，很明显就是滑动窗口类型。是的，虽然难度是困难，但其实细分下去是很简单的，但是我还是想分享一下我的做题历程，这道题很显然我第一眼望去就是PriorityQueue堆结构来实现。于是开始了。（这里我就不描述题目了）
手写堆的详细链接：https://blog.csdn.net/m0_51085029/article/details/121118435
public int[] maxSlidingWindow(int[] nums, int k) {
int []arr=new int [nums.length-k+1];
if(nums.length==0||k==0) return new int[0];
int index=0;
if(k>=nums.length){
arr[index]=Integer.MIN_VALUE;
for(int i=0;i{
@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub
return o2-o1;
}
}
但很显然PriorityQueue 这个结构有个很明显的缺点，，，就是无法对堆结构进行修改。
于是我衍生一个想法，手写堆结构实现。
public int[] maxSlidingWindow(int[] nums, int k) {
int n=nums.length;
int []arr=new int [n-k+1];
if(n==0||k==0) return new int [0];
if(k>=n){
Arrays.sort(nums);
return new int []{nums[n-1]};
}
int index=0;
int left=0;
int right=0;
int l=Integer.MIN_VALUE;
for(int i=0;i arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
public static void HeapBy(int[] arr, int index, int heapsize) {
int left = 2 * index + 1;
while (left < heapsize) {
// 左右孩子比较大小 并且左右孩子不能越界
int larget = left + 1 < heapsize && arr[left + 1] > arr[left] ? left + 1 : left;
larget = arr[larget] > arr[index] ? larget : index;
if (larget == index)
break;
swap(arr, index, larget);
index = larget;
left = index * 2 + 1;
}
}
public static void HeapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) {
HeapInsert(arr, i);
}
int index = arr.length;
swap(arr, 0, --index);
while (index > 0) {
HeapBy(arr, 0, index);
swap(arr, 0, --index);
}
}
public static void find(int[] arr, int index) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (arr[mid] > index) {
right = mid;
} else if (arr[mid] < index) {
left = mid + 1;
} else {
arr[mid] = Integer.MIN_VALUE;
//别小看这个break 这边起到
//很大的作用就是对于重复的数子不会多删
//debug好久才发现
break;
}
}
HeapSort(arr);
}
public static int poll(int []arr) {
int n=arr[arr.length-1];
int []dp=new int [arr.length-1];
for(int i=0;i
这个结构是可以实现的，但是后面的力扣数据给太大导致我的数组越界，我调试了一下时间超时，果然我手写的东西还是经不起大数据的考验，但是通过这一个改动。其实学到了不少！！所以分享给大家。当然有优化的地方还请各位大佬指出。
后面我又看了一个官方解析：
原来还可以这样：
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
PriorityQueue pq = new PriorityQueue(new Comparator() {
public int compare(int[] pair1, int[] pair2) {
return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
}
});
for (int i = 0; i < k; ++i) {
pq.offer(new int[]{nums[i], i});
}
int[] ans = new int[n - k + 1];
ans[0] = pq.peek()[0];
for (int i = k; i < n; ++i) {
pq.offer(new int[]{nums[i], i});
while (pq.peek()[1] <= i - k) {
pq.poll();
}
ans[i - k + 1] = pq.peek()[0];
}
return ans;
}
最后给大家最优版本：
其实就是用一个单调Deque队列来实现这一结构。
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
Deque deque = new linkedList();
for (int i = 0; i < k; ++i) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
}
int[] ans = new int[n - k + 1];
ans[0] = nums[deque.peekFirst()];
for (int i = k; i < n; ++i) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
while (deque.peekFirst() <= i - k) {
deque.pollFirst();
}
ans[i - k + 1] = nums[deque.peekFirst()];
}
return ans;
}
