滑动窗口最大值
给你一个整数数组 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
示例 2：
输入：nums = [1], k = 1
输出：[1]
题解
主要思路很简单，使用优先级队列每次将窗口的 value 加入到队列，然后逐渐移动窗口就可以每次取出来最大值；但是这里要注意的是，窗口移动时，需要 pop 窗口左边元素，同时 加入右边元素，但是队列在排序后如果遍历寻找窗口左边的元素再 poll 时间复杂度很高， 因此，我们选择将索引和值同时存到队列里面，每次我们不需要刻意去寻找窗口左边的值去 poll ，我们只需要判断当前队列的队头元素是否在窗口内，是则无影响，否则 poll ，这样我们就无需每次都删除窗口左边元素了
type IntMaxHeap [][2]int // 存储元素值以及索引
func (h IntMaxHeap) Len() int { return len(h) }
func (h IntMaxHeap) Less(i, j int) bool { return h[i][0] > h[j][0] }
func (h IntMaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntMaxHeap) Push(x any) {
*h = append(*h, x.([2]int))
}
func (h *IntMaxHeap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func maxSlidingWindow(nums []int, k int) []int {
ans := []int{}
q := &IntMaxHeap{}
heap.Init(q)
// 初始化窗口
for i := 0; i < k; i++ {
heap.Push(q, [2]int{nums[i], i})
}
ans = append(ans, (*q)[0][0])
for i := k; i < len(nums); i++ {
heap.Push(q, [2]int{nums[i], i})
for (*q)[0][1] <= i-k {
heap.Pop(q)
}
// heap.Push(q, [2]int{nums[i], i})
ans = append(ans, (*q)[0][0])
}
return ans
}
另外附一下堆的模板，当然如果是简单的情况，可以直接使用 sort.Intslice 代替
type IntMinHeap []int
func (h IntMinHeap) Len() int { return len(h) }
func (h IntMinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntMinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntMinHeap) Push(x any) {
*h = append(*h, x.(int))
}
func (h *IntMinHeap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
不得不说，使用 Go 写代码有时候真的很容易红温，生态确实比不上 Java， 用 Java写这个代码就非常舒服
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> b[0] - a[0]);
int[] ans = new int[nums.length - k + 1];
// 初始化窗口
for (int i = 0; i < k; i++) {
pq.offer(new int[] { nums[i], i });
}
ans[0] = pq.peek()[0];
for (int i = k; i < nums.length; 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;
}
}