239. 滑动窗口最大值 Sliding Window Maximum
给你一个整数数组 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]
提示：
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^41 <= k <= nums.length
代码1： 暴力枚举
package main import "fmt" func maxSlidingWindow(nums []int, k int) []int { ans := make([]int, len(nums)-k+1) for i := 0; i <= len(nums)-k; i++ { max := nums[i] for j := i + 1; j < i+k; j++ { if nums[j] > max { max = nums[j] } } ans[i] = max } return ans } func main() { nums := []int{1, 3, -1, -3, 5, 3, 6, 7} k := 3 fmt.Println(maxSlidingWindow(nums, k)) nums = []int{1} k = 1 fmt.Println(maxSlidingWindow(nums, k)) }
代码2： 双端队列
package main import "fmt" func maxSlidingWindow(nums []int, k int) []int { var ans []int q := make([]int, 0) // 双端队列，存放的是数字的下标 for i, num := range nums { if len(q) > 0 && q[0] < i-k+1 { // 当前滑动窗口的左端已离队列滑出，则要将该元素从队列中弹出 q = q[1:] } // 将当前数字与双端队列队尾数字比较，如果当前数字大于队列数字，则弹出队列。 // 这是因为当前数字更大，而队列中以前数字已经没有用处，我们可以弹出它们。 for len(q) > 0 && nums[q[len(q)-1]] < num { q = q[:len(q)-1] } // 将当前数字下标加入队列 q = append(q, i) // 到了一个滑动窗口的结束，将当前窗口中的最大值加入结果集中 if i >= k-1 { ans = append(ans, nums[q[0]]) } } return ans } func main() { nums := []int{1, 3, -1, -3, 5, 3, 6, 7} k := 3 fmt.Println(maxSlidingWindow(nums, k)) nums = []int{1} k = 1 fmt.Println(maxSlidingWindow(nums, k)) }
代码： 动态规划
package main import "fmt" func maxSlidingWindow(nums []int, k int) []int { n := len(nums) leftMax := make([]int, n) rightMax := make([]int, n) // 计算leftMax数组 for i := 0; i < n; i++ { if i%k == 0 { leftMax[i] = nums[i] } else { leftMax[i] = max(leftMax[i-1], nums[i]) } } // 计算rightMax数组 for i := n - 1; i >= 0; i-- { if i == n-1 || (i+1)%k == 0 { rightMax[i] = nums[i] } else { rightMax[i] = max(rightMax[i+1], nums[i]) } } // 获取每个窗口的最大值 ans := make([]int, n-k+1) for i := 0; i <= n-k; i++ { ans[i] = max(rightMax[i], leftMax[i+k-1]) } return ans } func max(x, y int) int { if x > y { return x } return y } func main() { nums := []int{1, 3, -1, -3, 5, 3, 6, 7} k := 3 fmt.Println(maxSlidingWindow(nums, k)) nums = []int{1} k = 1 fmt.Println(maxSlidingWindow(nums, k)) }
输出：
[3 3 5 5 6 7]
[1]
480. 滑动窗口中位数 Sliding Window Median
中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。
例如：
[2,3,4]，中位数是3[2,3]，中位数是(2 + 3) / 2 = 2.5
给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。
示例：
给出 nums = [1,3,-1,-3,5,3,6,7]，以及 k = 3。
窗口位置 中位数
--------------- -----
[1 3 -1] -3 5 3 6 7 1
1 [3 -1 -3] 5 3 6 7 -1
1 3 [-1 -3 5] 3 6 7 -1
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] 6
因此，返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]。
提示：
- 你可以假设
k始终有效，即：k始终小于等于输入的非空数组的元素个数。 - 与真实值误差在
10^-5以内的答案将被视作正确答案。
代码： 暴力枚举
package main import ( "fmt" "sort" ) func medianSlidingWindow(nums []int, k int) []float64 { n := len(nums) if k == 1 { ans := make([]float64, n) for i := 0; i < n; i++ { ans[i] = float64(nums[i]) } return ans } ans := make([]float64, n-k+1) for i := 0; i <= n-k; i++ { tmp := make([]int, k) copy(tmp, nums[i:i+k]) sort.Ints(tmp) if k%2 == 0 { ans[i] = float64(tmp[k/2-1]+tmp[k/2]) / 2 } else { ans[i] = float64(tmp[k/2]) } } return ans } func main() { nums := []int{1, 3, -1, -3, 5, 3, 6, 7} k := 3 fmt.Println(medianSlidingWindow(nums, k)) }
输出：
[1 -1 -1 3 5 6]
🌟 每日一练刷题专栏 🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
|
Rust每日一练 专栏 （2023.5.16~）更新中... |
|
Golang每日一练 专栏 （2023.3.11~）更新中... |
|
Python每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
C/C++每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
Java每日一练 专栏 （2023.3.11~2023.5.18）暂停更 |
