小说网站制作开源,阿里快速建站,wordpress设置文章标题,wordpress图片表单插件下载滑动窗口最大值
题目#xff1a;239. 滑动窗口最大值
给你一个整数数组 nums#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1#xff1…滑动窗口最大值
题目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] 1041 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)rfor r len(nums) {if nums[r] res[r-k] nums[r-k] res[r-k] {max_n nums[r-k1]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
}
