双端队列解leetcode之239-滑动窗口最大值

说来惭愧，这个题目我个人死磕了四天才最终理解。感谢这个视频，最终让我理解透了。还好没放弃，四天换来理解，也可以了。重点是要在双端队列中放入元素的索引值，而不是元素值本身

解题思路:

1. 定义一个双端队列，在这里用数组模拟
2. 当前元素同双端队列的尾部元素做比较，如果小，则出队，要一直出到队列为空，或者尾部元素大于当前元素
3. 满足第二步的条件后，将当前元素的索引放入双端队列
4. 因为窗口是滑动，要判断放入队列的索引值是否还有效，无效则出队
5. 达到窗口大小后，每次从队列的头部取数据即可，此时的头部值就是当前窗口的最大值

go示例代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


func maxSlidingWindow(nums []int, k int) []int {
    // 队列为1，空，或者K为1时，直接原样返回即可
	if len(nums) <= 1 || k == 1 {
		return nums
	}
	result := make([]int, 0)
	// queue里面记录的是索引
	queue := make([]int, 0)
	left := 0
	for i, v := range nums {
		// 左指针是否移动
		if i > k - 1 {
			left += 1
		}
		// 往queue里面加数据。新元素要大于尾部元素
		// queue[len(queue) - 1] 取queue的最后一个元素在nums的索引值
		// 所以元素值就是nums[queue[len(queue)-1]]
		for len(queue) > 0 && v > nums[queue[len(queue)-1]] {
			queue = queue[:len(queue)-1]
		}
        // 出完之后，就可以将当前元素的索引入队了
		queue = append(queue, i)
        
		// queue头部的索引是否还有效，因为指针移动，值不在滑动窗口内，就要失效
		if queue[0] < left {
			queue = queue[1:]
		}
        // 达到窗口大小后，就可以往结果集里面放数据。queue存储的是索引值
		if i >= k - 1 {
			result = append(result, nums[queue[0]])
		}
	}
	return result
}

文章目录