每日一题 --- 滑动窗口最大值[力扣][Go]

滑动窗口最大值

题目：239. 滑动窗口最大值

给你一个整数数组 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       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7

示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

方法一（模拟法，执行时间超过限制）：

可能这道题是困难的原因就是因为没办法使用模拟法来做。

func maxSlidingWindow(nums []int, k int) []int {//	滑动窗口，每次滑动判断新进的值与最大值谁大，如果不如最大值，最大值是否划出，r := k - 1res := make([]int, 0)max_n := nums[0]for i := r - k + 1; i <= r; i++ {if max_n < nums[i] {max_n = nums[i]}}res = append(res, max_n)r++for r < len(nums) {if nums[r] < res[r-k] && nums[r-k] == res[r-k] {max_n = nums[r-k+1]for i := r - k + 1; i <= r; i++ {if max_n < nums[i] {max_n = nums[i]}}res = append(res, max_n)} else if nums[r] >= res[r-k] {res = append(res, nums[r])} else if nums[r-k] != res[r-k] {res = append(res, res[r-k])}r++}return res
}

方法二：

单调队列，详细解析：代码随想录 (programmercarl.com)

// 单调队列
func maxSlidingWindow(nums []int, k int) []int {mq := Constructor239()res := make([]int, 0)for i := 0; i < k; i++ {mq.push(nums[i])}res = append(res, mq.front())for i := k; i < len(nums); i++ {mq.pop(nums[i-k])mq.push(nums[i])res = append(res, mq.front())}return res
}type MyQueue239 struct {queue []int
}func Constructor239() *MyQueue239 {return &MyQueue239{queue: make([]int, 0)}
}// pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
// push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止
func (q *MyQueue239) pop(x int) {if !q.Empty() && x == q.queue[0] {q.queue = q.queue[1:]}
}func (q *MyQueue239) push(x int) {for !q.Empty() && x > q.queue[len(q.queue)-1] {q.queue = q.queue[:len(q.queue)-1]}q.queue = append(q.queue, x)
}func (q *MyQueue239) front() int {return q.queue[0]
}func (q *MyQueue239) Empty() bool {if len(q.queue) == 0 {return true}return false
}