 滑动窗口最大值)
LeetCode-Go 题解 239. Sliding Window Maximum单调双端队列实现 O(n) 滑动窗口最大值【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文讲解 LeetCode 第 239 题 Sliding Window Maximum滑动窗口最大值在 LeetCode-Go 仓库中的完整解法。这道题是滑动窗口类问题与单调队列Monotonic Deque的经典代表作仓库在leetcode/0239.Sliding-Window-Maximum目录下同时提供了暴力枚举与双端队列两种实现并配有单元测试。读完本文你将掌握从 O(n·k) 暴力解法到 O(n) 线性时间最优解的全部推导路径并能在 Go 中亲手复现基于双端队列的滑动窗口最大值算法。题目描述给定一个数组nums有一个大小为k的滑动窗口从数组的最左侧移动到最右侧。你只可以看到在滑动窗口k内的数字。滑动窗口每次只向右移动一位。返回滑动窗口最大值max sliding window。示例Input: nums [1,3,-1,-3,5,3,6,7], and k 3 Output: [3,3,5,5,6,7] Explanation: Window position Max --------------- ----- [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注意你可以假设k总是有效的即对非空数组有1 ≤ k ≤ 数组长度。Follow up你能在线性时间内解决它吗Could you solve it in linear time?题目大意给定一个数组nums一个大小为k的滑动窗口从数组最左侧滑到最右侧每次只向右移动一位输出每次移动后窗口内的最大值。最终结果数组的长度为n - k 1。思路一暴力解法两层循环O(n·k)最直接的想法是对每个窗口位置遍历窗口内的k个元素找出最大值。仓库在 239. Sliding Window Maximum.go 中以maxSlidingWindow1实现了这一版本// 解法一 暴力解法 O(nk) func maxSlidingWindow1(a []int, k int) []int { res : make([]int, 0, k) n : len(a) if n 0 { return []int{} } for i : 0; i n-k; i { max : a[i] for j : 1; j k; j { if max a[ij] { max a[ij] } } res append(res, max) } return res }外层循环控制窗口左端点i范围是0到n-k共n-k1个窗口内层循环在窗口内扫描k个元素用max变量维护当前窗口最大值数组为空时直接返回空切片避免越界。时间复杂度为 O(n·k)空间复杂度为 O(1)不计输出数组。当k接近n时退化为 O(n²)仅适合作为正确性参照实现。思路二优先队列最大堆O(n·log n)另一种思路是用优先队列最大堆。每移动一次窗口向优先队列中新增一个元素并删除一个已经滑出窗口的元素堆顶即当前窗口的最大值。每次堆操作Push/Pop的复杂度为 O(log n)共 n 次操作因此整体时间复杂度为 O(n·log n)。LeetCode-Go 仓库在 structures/PriorityQueue.go 中提供了一套基于container/heap接口的通用优先队列实现PQ类型及Push/Pop/update方法可用于这类动态取最值场景。不过与双端队列解法相比堆方案多出 O(log n) 的对数因子不是本题的最优解。思路三双端队列单调队列O(n) 最优解最优解法使用双端队列Deque。核心思想是让队列中的元素始终按数组下标递增排列、对应数值单调递减从而保证队列的一头队首永远存的是当前窗口的最大值队列的另外一头存的是比最大值小的值且这些值按从大到小递减排列新元素入队前把队尾所有比它小的值全部出队因为它们不可能再成为窗口最大值当窗口滑动导致队首下标滑出窗口时将其出队。在保证了双端队列队首即是窗口最大值后每个元素至多入队、出队各一次时间复杂度为 O(n)空间复杂度为 O(k)。这正是题目 Follow up 所要求的线性时间解法。仓库在 239. Sliding Window Maximum.go 中实现了这一最优解法// 解法二 双端队列 Deque func maxSlidingWindow(nums []int, k int) []int { if len(nums) 0 || len(nums) k { return make([]int, 0) } window : make([]int, 0, k) // store the index of nums result : make([]int, 0, len(nums)-k1) for i, v : range nums { // if the left-most index is out of window, remove it if i k window[0] i-k { window window[1:] } for len(window) 0 nums[window[len(window)-1]] v { // maintain window window window[0 : len(window)-1] } window append(window, i) // store the index of nums if i k-1 { result append(result, nums[window[0]]) // the left-most is the index of max value in nums } } return result }逐行剖析前置校验len(nums) 0 || len(nums) k时直接返回空切片。注意这里用make([]int, 0)返回的是非 nil 空切片与测试中对空数组的期望保持一致。数据结构window切片存储的是数组下标而非数值本身result预分配len(nums)-k1容量即滑动窗口的总个数。存储下标而不是值是为了后续能判断元素是否已滑出窗口。淘汰过期元素if i k window[0] i-k { window window[1:] }。当窗口已经滑动满k步后每次迭代检查队首下标是否落在当前窗口[i-k1, i]之外若是则从队首出队。window window[1:]本质上是切片头部弹出正是双端队列的一端。维护单调性for len(window) 0 nums[window[len(window)-1]] v从队尾开始把所有数值小于当前值v的下标弹出。因为这些较小值在v存在期间不可能成为最大值v更新且更靠右存活时间更长。这是单调递减队列的精髓队尾弹出对应双端队列的另一端操作。入队与产出结果将当前下标i入队当i k-1即第一个完整窗口形成后nums[window[0]]就是当前窗口的最大值追加到result。手工推演示例以nums [1,3,-1,-3,5,3,6,7]、k 3为例window中存储下标括号内是实际值iv操作window下标/值result01入队[0/1]—13弹出 1 再入队[1/3]—2-1入队[1/3, 2/-1][3]3-3下标 1 过期出队-3 入队[2/-1, 3/-3][3, 3]45弹出 -3、-1 再入队[4/5][3, 3, 5]53入队[4/5, 5/3][3, 3, 5, 5]66弹出 3、5 再入队[6/6][3, 3, 5, 5, 6]77弹出 6 再入队[7/7][3, 3, 5, 5, 6, 7]可以看到队首始终指向当前窗口的最大值最终输出与题目示例完全一致[3, 3, 5, 5, 6, 7]。边界条件与测试验证三种边界情况仓库测试文件 239. Sliding Window Maximum_test.go 覆盖了三种典型输入正常窗口nums [1,3,-1,-3,5,3,6,7]k 3期望[3,3,5,5,6,7]空数组nums []k 3期望[]。这验证了暴力解法n 0分支与双端队列解法len(nums) 0分支的正确性窗口大于数组nums [1,2]k 3期望[]。这验证了len(nums) k的守卫条件。测试使用reflect.DeepEqual对两种解法的输出与期望结果做严格比较任何长度或元素不一致都会触发t.Fatalf报错got : maxSlidingWindow(p.one, p.k) if len(got) ! len(a.one) || (len(got) 0 !reflect.DeepEqual(got, a.one)) { t.Fatalf(maxSlidingWindow(%v, %d) %v, want %v, p.one, p.k, got, a.one) }运行测试进入仓库根目录后可直接针对该题运行测试go test -v -run Test_Problem239 ./leetcode/0239.Sliding-Window-Maximum/整个仓库的测试脚本 gotest.sh 采用go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...的方式对全部leetcode包一次性生成覆盖率报告保证包括本题在内的所有题解都能被测试用例完整覆盖。复杂度对比总结解法核心数据结构时间复杂度空间复杂度适用场景暴力枚举maxSlidingWindow1无两层循环O(n·k)O(1)小规模数据、正确性参照优先队列最大堆堆O(n·log n)O(k)需要动态取最值的通用场景双端队列maxSlidingWindow单调递减队列O(n)O(k)本题最优解线性时间其中双端队列解法的核心洞察是队首永远保存当前窗口的最大值队尾按递减序保存有潜力成为最大值的候选项同时利用下标判断元素是否过期。每个元素至多入队一次、出队一次因此整体是严格线性的 O(n)。这一单调队列模式不仅适用于本题也是处理滑动窗口极值类问题如固定窗口最小值、最大最小差值受限子数组等的通用武器值得熟练掌握。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode-Go 题解 239. Sliding Window Maximum单调双端队列实现 O(n) 滑动窗口最大值【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文讲解 LeetCode 第 239 题 Sliding Window Maximum滑动窗口最大值在 LeetCode-Go 仓库中的完整解法。这道题是滑动窗口类问题与单调队列Monotonic Deque的经典代表作仓库在leetcode/0239.Sliding-Window-Maximum目录下同时提供了暴力枚举与双端队列两种实现并配有单元测试。读完本文你将掌握从 O(n·k) 暴力解法到 O(n) 线性时间最优解的全部推导路径并能在 Go 中亲手复现基于双端队列的滑动窗口最大值算法。题目描述给定一个数组nums有一个大小为k的滑动窗口从数组的最左侧移动到最右侧。你只可以看到在滑动窗口k内的数字。滑动窗口每次只向右移动一位。返回滑动窗口最大值max sliding window。示例Input: nums [1,3,-1,-3,5,3,6,7], and k 3 Output: [3,3,5,5,6,7] Explanation: Window position Max --------------- ----- [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注意你可以假设k总是有效的即对非空数组有1 ≤ k ≤ 数组长度。Follow up你能在线性时间内解决它吗Could you solve it in linear time?题目大意给定一个数组nums一个大小为k的滑动窗口从数组最左侧滑到最右侧每次只向右移动一位输出每次移动后窗口内的最大值。最终结果数组的长度为n - k 1。思路一暴力解法两层循环O(n·k)最直接的想法是对每个窗口位置遍历窗口内的k个元素找出最大值。仓库在 239. Sliding Window Maximum.go 中以maxSlidingWindow1实现了这一版本// 解法一 暴力解法 O(nk) func maxSlidingWindow1(a []int, k int) []int { res : make([]int, 0, k) n : len(a) if n 0 { return []int{} } for i : 0; i n-k; i { max : a[i] for j : 1; j k; j { if max a[ij] { max a[ij] } } res append(res, max) } return res }外层循环控制窗口左端点i范围是0到n-k共n-k1个窗口内层循环在窗口内扫描k个元素用max变量维护当前窗口最大值数组为空时直接返回空切片避免越界。时间复杂度为 O(n·k)空间复杂度为 O(1)不计输出数组。当k接近n时退化为 O(n²)仅适合作为正确性参照实现。思路二优先队列最大堆O(n·log n)另一种思路是用优先队列最大堆。每移动一次窗口向优先队列中新增一个元素并删除一个已经滑出窗口的元素堆顶即当前窗口的最大值。每次堆操作Push/Pop的复杂度为 O(log n)共 n 次操作因此整体时间复杂度为 O(n·log n)。LeetCode-Go 仓库在 structures/PriorityQueue.go 中提供了一套基于container/heap接口的通用优先队列实现PQ类型及Push/Pop/update方法可用于这类动态取最值场景。不过与双端队列解法相比堆方案多出 O(log n) 的对数因子不是本题的最优解。思路三双端队列单调队列O(n) 最优解最优解法使用双端队列Deque。核心思想是让队列中的元素始终按数组下标递增排列、对应数值单调递减从而保证队列的一头队首永远存的是当前窗口的最大值队列的另外一头存的是比最大值小的值且这些值按从大到小递减排列新元素入队前把队尾所有比它小的值全部出队因为它们不可能再成为窗口最大值当窗口滑动导致队首下标滑出窗口时将其出队。在保证了双端队列队首即是窗口最大值后每个元素至多入队、出队各一次时间复杂度为 O(n)空间复杂度为 O(k)。这正是题目 Follow up 所要求的线性时间解法。仓库在 239. Sliding Window Maximum.go 中实现了这一最优解法// 解法二 双端队列 Deque func maxSlidingWindow(nums []int, k int) []int { if len(nums) 0 || len(nums) k { return make([]int, 0) } window : make([]int, 0, k) // store the index of nums result : make([]int, 0, len(nums)-k1) for i, v : range nums { // if the left-most index is out of window, remove it if i k window[0] i-k { window window[1:] } for len(window) 0 nums[window[len(window)-1]] v { // maintain window window window[0 : len(window)-1] } window append(window, i) // store the index of nums if i k-1 { result append(result, nums[window[0]]) // the left-most is the index of max value in nums } } return result }逐行剖析前置校验len(nums) 0 || len(nums) k时直接返回空切片。注意这里用make([]int, 0)返回的是非 nil 空切片与测试中对空数组的期望保持一致。数据结构window切片存储的是数组下标而非数值本身result预分配len(nums)-k1容量即滑动窗口的总个数。存储下标而不是值是为了后续能判断元素是否已滑出窗口。淘汰过期元素if i k window[0] i-k { window window[1:] }。当窗口已经滑动满k步后每次迭代检查队首下标是否落在当前窗口[i-k1, i]之外若是则从队首出队。window window[1:]本质上是切片头部弹出正是双端队列的一端。维护单调性for len(window) 0 nums[window[len(window)-1]] v从队尾开始把所有数值小于当前值v的下标弹出。因为这些较小值在v存在期间不可能成为最大值v更新且更靠右存活时间更长。这是单调递减队列的精髓队尾弹出对应双端队列的另一端操作。入队与产出结果将当前下标i入队当i k-1即第一个完整窗口形成后nums[window[0]]就是当前窗口的最大值追加到result。手工推演示例以nums [1,3,-1,-3,5,3,6,7]、k 3为例window中存储下标括号内是实际值iv操作window下标/值result01入队[0/1]—13弹出 1 再入队[1/3]—2-1入队[1/3, 2/-1][3]3-3下标 1 过期出队-3 入队[2/-1, 3/-3][3, 3]45弹出 -3、-1 再入队[4/5][3, 3, 5]53入队[4/5, 5/3][3, 3, 5, 5]66弹出 3、5 再入队[6/6][3, 3, 5, 5, 6]77弹出 6 再入队[7/7][3, 3, 5, 5, 6, 7]可以看到队首始终指向当前窗口的最大值最终输出与题目示例完全一致[3, 3, 5, 5, 6, 7]。边界条件与测试验证三种边界情况仓库测试文件 239. Sliding Window Maximum_test.go 覆盖了三种典型输入正常窗口nums [1,3,-1,-3,5,3,6,7]k 3期望[3,3,5,5,6,7]空数组nums []k 3期望[]。这验证了暴力解法n 0分支与双端队列解法len(nums) 0分支的正确性窗口大于数组nums [1,2]k 3期望[]。这验证了len(nums) k的守卫条件。测试使用reflect.DeepEqual对两种解法的输出与期望结果做严格比较任何长度或元素不一致都会触发t.Fatalf报错got : maxSlidingWindow(p.one, p.k) if len(got) ! len(a.one) || (len(got) 0 !reflect.DeepEqual(got, a.one)) { t.Fatalf(maxSlidingWindow(%v, %d) %v, want %v, p.one, p.k, got, a.one) }运行测试进入仓库根目录后可直接针对该题运行测试go test -v -run Test_Problem239 ./leetcode/0239.Sliding-Window-Maximum/整个仓库的测试脚本 gotest.sh 采用go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...的方式对全部leetcode包一次性生成覆盖率报告保证包括本题在内的所有题解都能被测试用例完整覆盖。复杂度对比总结解法核心数据结构时间复杂度空间复杂度适用场景暴力枚举maxSlidingWindow1无两层循环O(n·k)O(1)小规模数据、正确性参照优先队列最大堆堆O(n·log n)O(k)需要动态取最值的通用场景双端队列maxSlidingWindow单调递减队列O(n)O(k)本题最优解线性时间其中双端队列解法的核心洞察是队首永远保存当前窗口的最大值队尾按递减序保存有潜力成为最大值的候选项同时利用下标判断元素是否过期。每个元素至多入队一次、出队一次因此整体是严格线性的 O(n)。这一单调队列模式不仅适用于本题也是处理滑动窗口极值类问题如固定窗口最小值、最大最小差值受限子数组等的通用武器值得熟练掌握。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
