LeetCode 热题 HOT100（三）：子串进阶与普通数组（Go 实现）
🥰个人主页：会编程的土豆（欢迎来访）
💎作者简介：后端学习者
❄️个人专栏：数据结构与算法，数据库，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)。最优解用单调队列（存下标）：
- 队列内下标对应的值从大到小
- 新元素入队前，从队尾弹出所有「值 ≤ 当前值」的下标（它们不可能再成为最大值）
- 队头若滑出窗口（下标 ≤ i-k），弹出
- 窗口形成后，队头就是当前最大值下标
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'。思路分析
变长滑动窗口经典题：
- 统计
t的字符需求need，以及还需满足的「有效字符种类数」needKinds - 右指针扩张，更新窗口计数；某字符刚好凑齐时
valid++ - 当
valid == needKinds，说明窗口已覆盖，尝试收缩左指针，并记录最短子串 - 左端字符不够时
valid--，继续扩张
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]。思路分析
- 按区间左端点排序
- 遍历：若当前区间与结果中最后一个区间重叠（
start <= lastEnd），则合并，更新右端点为两者较大值 - 否则直接追加新区间
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)：
- 整体反转：
[1,2,3,4,5,6,7]→[7,6,5,4,3,2,1] - 反转前
k个：[5,6,7,4,3,2,1] - 反转后
n-k个：[5,6,7,1,2,3,4]
注意先对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 刷完！