🥰个人主页：会编程的土豆（欢迎来访）
💎作者简介：后端学习者 ❄️个人专栏：数据结构与算法，数据库，leetcode ✨那些你一个人走过的夜路，终将化作照亮未来的光
本文覆盖力扣「热题 100」学习计划第 11～15 题，全部使用 Go 实现。
第 10 题「和为 K 的子数组」见上一篇；本篇从滑动窗口最大值开始。
题单入口：LeetCode 热题 100
239. 滑动窗口最大值
难度： 困难 标签： 队列、数组、滑动窗口、单调队列、堆（优先队列） 题目链接： 239. 滑动窗口最大值
题目描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例：
输入：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
思路分析
暴力每个窗口扫一遍是 O(nk)。最优解用 单调队列（存下标）：
Go 代码
func maxSlidingWindow(nums []int, k int) []int {
n := len(nums)
res := make([]int, 0, n-k+1)
deque := make([]int, 0) // 存下标，对应值单调递减
for i, num := range nums {
// 弹出队尾较小元素
for len(deque) > 0 && nums[deque[len(deque)-1]] <= num {
deque = deque[:len(deque)-1]
}
deque = append(deque, i)
// 弹出滑出窗口的队头
if deque[0] <= i-k {
deque = deque[1:]
}
// 窗口已形成
if i >= k-1 {
res = append(res, nums[deque[0]])
}
}
return res
}
复杂度
- 时间复杂度：O(n)，每个下标最多入队、出队一次
- 空间复杂度：O(k)
76. 最小覆盖子串
难度： 困难 标签： 哈希表、字符串、滑动窗口 题目链接： 76. 最小覆盖子串
题目描述
给你一个字符串 s、一个字符串 t。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""。
注意：对于 t 中重复字符，子串中该字符数量必须不少于 t 中该字符数量。
示例：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
思路分析
变长滑动窗口经典题：
Go 代码
func minWindow(s string, t string) string {
if len(s) < len(t) || len(t) == 0 {
return ""
}
need := make(map[byte]int)
for i := 0; i < len(t); i++ {
need[t[i]]++
}
needKinds := len(need)
window := make(map[byte]int)
valid := 0
left := 0
start, minLen := 0, len(s)+1
for right := 0; right < len(s); right++ {
c := s[right]
if _, ok := need[c]; ok {
window[c]++
if window[c] == need[c] {
valid++
}
}
for valid == needKinds && left <= right {
if right-left+1 < minLen {
minLen = right – left + 1
start = left
}
d := s[left]
left++
if _, ok := need[d]; ok {
if window[d] == need[d] {
valid–
}
window[d]–
}
}
}
if minLen == len(s)+1 {
return ""
}
return s[start : start+minLen]
}
复杂度
- 时间复杂度：O(|s| + |t|)
- 空间复杂度：O(|Σ|)
53. 最大子数组和
难度： 中等 标签： 数组、分治、动态规划 题目链接： 53. 最大子数组和
题目描述
给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6。
思路分析
Kadane 算法（可看作一维 DP）：
- cur：以当前元素结尾的最大子段和
- 转移：cur = max(nums[i], cur + nums[i])
- 含义：前面累加和若为负，不如从当前重新开始
同时用 ans 维护全局最大值。
Go 代码
func maxSubArray(nums []int) int {
cur, ans := nums[0], nums[0]
for i := 1; i < len(nums); i++ {
if cur > 0 {
cur += nums[i]
} else {
cur = nums[i]
}
if cur > ans {
ans = cur
}
}
return ans
}
复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(1)
56. 合并区间
难度： 中等 标签： 数组、排序 题目链接： 56. 合并区间
题目描述
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠，将它们合并为 [1,6]。
思路分析
Go 代码
func merge(intervals [][]int) [][]int {
if len(intervals) == 0 {
return nil
}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
res := [][]int{intervals[0]}
for i := 1; i < len(intervals); i++ {
last := res[len(res)-1]
cur := intervals[i]
if cur[0] <= last[1] {
if cur[1] > last[1] {
last[1] = cur[1]
}
} else {
res = append(res, cur)
}
}
return res
}
记得导入：import "sort"
复杂度
- 时间复杂度：O(n log n)，主要在排序
- 空间复杂度：O(log n)（排序栈空间，不计返回数组）
189. 轮转数组
难度： 中等 标签： 数组、数学、双指针 题目链接： 189. 轮转数组
题目描述
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例：
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
思路分析
经典「三次反转」，空间 O(1)：
注意先对 k 取模，避免 k >= n。
Go 代码
func rotate(nums []int, k int) {
n := len(nums)
k %= n
reverse(nums, 0, n-1)
reverse(nums, 0, k-1)
reverse(nums, k, n-1)
}
func reverse(nums []int, left, right int) {
for left < right {
nums[left], nums[right] = nums[right], nums[left]
left++
right–
}
}
复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(1)
小结
| 滑动窗口最大值 | 单调队列 | O(n) |
| 最小覆盖子串 | 变长滑动窗口 | O(n) |
| 最大子数组和 | Kadane / 一维 DP | O(n) |
| 合并区间 | 排序 + 线性合并 | O(n log n) |
| 轮转数组 | 三次反转 | O(n) |
前 15 题进度
| 1～5 | 两数之和 … 盛最多水的容器 | 第一篇 |
| 6～10 | 三数之和 … 和为 K 的子数组 | 第二篇 |
| 11～15 | 滑动窗口最大值 … 轮转数组 | 本文 |
下一篇可继续写普通数组剩余题（除自身以外数组的乘积、缺失的第一个正数）以及矩阵、链表专题。
如果对你有帮助，欢迎点赞收藏，一起把 Hot100 刷完！
