用于分享leetcode每月中每日一题的解法，希望能抛砖引玉，互相进步
GitHub - kingeasternsun/leetcode-cn: leetcode with golang rust 觉得有帮助 还请赏个 
[239. 滑动窗口最大值]
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sliding-window-maximum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
代码内置详细注释
package leetcode
//224ms
func maxSlidingWindow(nums []int, k int) []int {
if len(nums) < k {
return nil
}
//使用单调队列来实现
monoQueue := make([]int, 0)
res := make([]int, 0) //保存结果
for i, v := range nums {
//从后往前，如果比monoQueue的最后一个要大，就弹出最后一个.
for len(monoQueue) > 0 {
if v > monoQueue[len(monoQueue)-1] {
monoQueue = monoQueue[:len(monoQueue)-1] //弹出
} else {
break //注意如果遇到比monoQueue最后一个要小 或 相等 就需要停止弹出了
}
}
//追加v到monoQueue里面
monoQueue = append(monoQueue, v)
//窗口长度还没有满k
if i < k-1 { //注意这里是要小于k-1
continue
}
//刚好满k
if i == k-1 {
res = append(res, monoQueue[0])
continue
}
//sliding窗口最左边的要移除
top := nums[i-k]
//top就是最大值，那么monoque需要把左边的也移除
if top == monoQueue[0] {
monoQueue = monoQueue[1:]
}
res = append(res, monoQueue[0])
}
return res
}
跟239类似的题目是1696题，所以在下面也贴出来
[1696. 跳跃游戏 VI]
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一开始你在下标 0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。也就是说，你可以从下标 i 跳到 [i + 1， min(n - 1, i + k)] 包含 两个端点的任意位置。
你的目标是到达数组最后一个位置（下标为 n - 1 ），你的 得分 为经过的所有数字之和。
请你返回你能得到的 最大得分 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game-vi
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
代码内带详细注释
maxResult_timeout是没有使用单调队列提交超时的做法
package leetcode
//https://github.com/kingeasternsun/leetcode-cn
import "math"
//dp 超时
func maxResult_timeout(nums []int, k int) int {
if len(nums) == 0 {
return 0
}
dp := make([]int, len(nums)) //表示跳在第i个位置的最大得分
dp[0] = nums[0]
for i := 1; i < len(nums); i++ {
beg := i - k
if beg < 0 {
beg = 0
}
dp[i] = maxOfSlice(dp[beg:i]) + nums[i]
}
return dp[len(nums)-1]
}
func maxOfSlice(dp []int) int {
res := math.MinInt32
for _, v := range dp {
if v > res {
res = v
}
}
return res
}
func maxResult(nums []int, k int) int {
if len(nums) == 0 {
return 0
}
dp := make([]int, len(nums)) //表示跳在第i个位置的最大得分
dp[0] = nums[0]
monoQueue := []int{nums[0]} //基于dp的滑窗
for i := 1; i < len(nums); i++ {
// dp[i] = maxOfSlice(dp[beg:i]) + nums[i]
//类似 239题目，利用单调队列
tmpV := monoQueue[0] + nums[i]
dp[i] = tmpV
//处理滑窗
for len(monoQueue) > 0 {
//tmpV比滑窗最后边的要大，就把最右边的剔除
if tmpV > monoQueue[len(monoQueue)-1] {
monoQueue = monoQueue[:len(monoQueue)-1]
} else {
break
}
}
monoQueue = append(monoQueue, tmpV)
// 如果当前sliding的大小超过了k，就需要从dp中剔除左边的一个,时刻让sliding窗口的大小最大为k,
// 所以每次只需要剔除滑窗左边的一个(也就是i-k位置上的那个)就可以了
if i >= k {
//如果dp[i-k]刚好是最大值 ,monoQueue也需要移除左边的最大值
if dp[i-k] == monoQueue[0] {
monoQueue = monoQueue[1:]
}
}
}
return dp[len(nums)-1]
}
