【LeetCode Solutions】LeetCode 热题 100 题解（11 ~ 15）

CONTENTS

• 子串 - LeetCode 239. 滑动窗口最大值（困难）
• 子串 - LeetCode 76. 最小覆盖子串（困难）
• 普通数组 - LeetCode 53. 最大子数组和（中等）
• 普通数组 - LeetCode 56. 合并区间（中等）
• 普通数组 - LeetCode 189. 轮转数组（中等）

子串 - LeetCode 239. 滑动窗口最大值（困难）

【题目描述】

给你一个整数数组 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<=1 0 5 1 <= nums.length <= 10^5 1<=nums.length<=105
−1 0 4 <=nums[i]<=1 0 4 -10^4 <= nums[i] <= 10^4 −104<=nums[i]<=104
$1<=k<=nums.length$

【分析】

非常经典的单调队列问题，具体分析可以跳转至：【模板题】单调队列 / 洛谷P1886 滑动窗口。

简单来说就是如果新来的数大于等于他前面的数，那么他前面的数就没有任何利用价值了，因此最后会维护出一个单调递减的队列，队头元素即为当前滑动窗口的最大值。同理如果要求最小值就维护一个单调递增队列即可。

【代码】

class Solution {public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> Q; // 存放元素下标 vector<int> res; for (int i = 0; i < nums.size(); i++) { if (Q.size() && i - Q.front() == k) Q.pop_front(); while (Q.size() && nums[i] >= nums[Q.back()]) Q.pop_back(); Q.push_back(i); if (i >= k - 1) res.push_back(nums[Q.front()]); } return res; }};

子串 - LeetCode 76. 最小覆盖子串（困难）

【题目描述】

给你一个字符串 s、一个字符串 t。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 \"\"。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

【示例 1】

输入：s = \"ADOBECODEBANC\", t = \"ABC\"输出：\"BANC\"解释：最小覆盖子串 \"BANC\" 包含来自字符串 t 的 \'A\'、\'B\' 和 \'C\'。

【示例 2】

输入：s = \"a\", t = \"a\"输出：\"a\"解释：整个字符串 s 是最小覆盖子串。

【示例 3】

输入: s = \"a\", t = \"aa\"输出: \"\"解释: t 中两个字符 \'a\' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。

【提示】

1≤s.length,t.length≤1 0 5 1\\le s.length, t.length\\le 10^5 1≤s.length,t.length≤105
s 和 t 由英文字母组成

【分析】

本题是滑动窗口的一个经典的应用，我们枚举 s 中的每个右端点 $i$，对于每个 $i$ 都找出最近的一个左端点 $j$，使得 s[j, i] 中包含 t 中的所有字符。

能用滑动窗口（双指针）的题目一定要具有单调性，即当 $i$ 往右移动的过程中 $j$ 一定不会往左移动。假设 s[j, i] 中已经包含 t 中的所有字符，那么当 $i$ 向右移动变为 i ′ i\' i′ 后 s[j, i\'] 一定也包含 t 中的所有字符，因此 $j$ 不可能往左移动变成 s[j\', i\']。

还有一个问题是如何快速判断当前区间中是否包含 t 中的所有字符，我们可以用哈希表分别统计 t 中每个字符出现的次数（t_cnt）以及滑动窗口内每个字符出现的次数（s_cnt），然后使用一个变量 cnt 统计 t 中有多少字符被滑动窗口包含了，如果 cnt 等于 t 的长度则说明全部字符以及被包含了，那么如何精准统计 cnt 呢？分情况讨论即可：

• 若当前字符 c 在滑动窗口中出现的次数已经大于 t 中该字符的数量则不累计 cnt；
• 若当前字符 c 在滑动窗口中出现的次数小于等于 t 中该字符的数量则将 cnt 加一。

如果字符 s[j] 出现的次数大于 t 中该字符的数量则可以将 $j$ 向右移动。

【代码】

class Solution {public: string minWindow(string s, string t) { unordered_map<char, int> s_cnt, t_cnt; int cnt = 0; string res; for (auto &c: t) t_cnt[c]++; for (int i = 0, j = 0; i < s.size(); i++) { s_cnt[s[i]]++; if (s_cnt[s[i]] <= t_cnt[s[i]]) cnt++; while (s_cnt[s[j]] > t_cnt[s[j]]) s_cnt[s[j]]--, j++; if (cnt == t.size() && (res.empty() || i - j + 1 < res.size())) res = s.substr(j, i - j + 1); } return res; }};

普通数组 - LeetCode 53. 最大子数组和（中等）

【题目描述】

给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中连续的非空元素序列。

【示例 1】

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]输出：6解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

【示例 2】

输入：nums = [1]输出：1

【示例 3】

输入：nums = [5,4,-1,7,8]输出：23

【提示】

1≤nums.length≤1 0 5 1\\le nums.length\\le 10^5 1≤nums.length≤105
−1 0 4 ≤nums[i]≤1 0 4 -10^4\\le nums[i]\\le 10^4 −104≤nums[i]≤104

【分析】

我们先分析 $O(n)$ 的算法，用动态规划考虑：令 $f[i]$ 表示所有以 nums[i] 结尾的区间中的最大和，那么状态转移有以下两种情况：

• 区间长度等于1：f[i] = nums[i]；
• 区间长度大于1：f[i] = f[i - 1] + nums[i]

因此可以得到状态转移方程为：f[i] = max(nums[i], f[i - 1] + nums[i]) = nums[i] + max(0, f[i - 1])，由于 f[i] 只和 f[i - 1] 有关，因此我们可以只使用一个变量记录 f[i - 1] 的值即可。

现在我们考虑如何用分治法求解，其实分治法就是线段树维护动态最大字段和的简化版，当前数组的最大子段所在的区间可能有以下几种情况：

• 在左子区间中，结果即为左子区间的最大子段；
• 在右子区间中，结果即为右子区间的最大子段；
• 横跨左右两个子区间，结果即为左子区间的最大后缀加上右子区间的最大前缀。

求解最大前缀与最大后缀时可能还会有以下几种情况：

• 最大前缀横跨左右两个子区间，那么最大前缀为左子区间的总和加上右子区间的最大前缀；
• 最大后缀横跨左右两个子区间，那么最大后缀为右子区间的总和加上左子区间的最大后缀。

因此我们需要处理出每个区间的最大子段、最大前缀、最大后缀以及总长度这四个信息。

【代码】

【动态规划实现】

class Solution {public: int maxSubArray(vector<int>& nums) { int res = INT_MIN; for (int i = 0, f = 0; i < nums.size(); i++) f = nums[i] + max(f, 0), res = max(res, f); return res; }};

【分治法实现】

class Solution {public: struct Node { int sum, lmax, rmax, tmax; // 区间和，最大前缀，最大后缀，最大子段和 }; int maxSubArray(vector<int>& nums) { auto t = build(nums, 0, nums.size() - 1); return t.tmax; } Node build(vector<int>& nums, int l, int r) { if (l == r) return { nums[l], nums[l], nums[l], nums[l] }; // 递归到了长度为 1 的结点 int mid = l + r >> 1; auto lnode = build(nums, l, mid), rnode = build(nums, mid + 1, r); // 线段树中的 pushup 操作 Node res; res.sum = lnode.sum + rnode.sum; res.lmax = max(lnode.lmax, lnode.sum + rnode.lmax); res.rmax = max(rnode.rmax, rnode.sum + lnode.rmax); res.tmax = max(max(lnode.tmax, rnode.tmax), lnode.rmax + rnode.lmax); return res; }};

普通数组 - LeetCode 56. 合并区间（中等）

【题目描述】

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_i, end_i]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

【示例 1】

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]输出：[[1,6],[8,10],[15,18]]解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

【示例 2】

输入：intervals = [[1,4],[4,5]]输出：[[1,5]]解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

【提示】

1≤intervals.length≤1 0 4 1\\le intervals.length\\le 10^4 1≤intervals.length≤104
$intervals[i].length==2$
0≤star t i ≤en d i ≤1 0 4 0\\le start_i\\le end_i\\le 10^4 0≤starti​≤endi​≤104

【分析】

区间合并模板题，是一个贪心问题，先将所有区间按左端点排序，然后遍历每个区间，并记录每个新区间的左右端点 $l,r$，若当前区间 $i$ 的左端点不在 $[l,r]$ 中，说明已经没办法合并了，$[l,r]$ 就是一个新区间，将其记录下来，然后将 $l,r$ 更新成当前区间的左右端点；若当前区间 $i$ 的左端点在 $[l,r]$ 中，那么新区间的右端点可能会更新，即 r = max(r, intervals[i][1])。

【代码】

class Solution {public: vector<vector<int>> merge(vector<vector<int>>& intervals) { vector<vector<int>> res; sort(intervals.begin(), intervals.end()); int l = intervals[0][0], r = intervals[0][1]; for (int i = 1; i < intervals.size(); i++) if (intervals[i][0] > r) { res.push_back({l, r}); l = intervals[i][0], r = intervals[i][1]; } else r = max(r, intervals[i][1]); res.push_back({l, r}); // 注意别忘了最后一段 return res; }};

普通数组 - LeetCode 189. 轮转数组（中等）

【题目描述】

给定一个整数数组 nums，将数组中的元素向右轮转 $k$ 个位置，其中 $k$ 是非负数。

【示例 1】

输入: 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]

【示例 2】

输入：nums = [-1,-100,3,99], k = 2输出：[3,99,-1,-100]解释: 向右轮转 1 步: [99,-1,-100,3]向右轮转 2 步: [3,99,-1,-100]

【提示】

1<=nums.length<=1 0 5 1 <= nums.length <= 10^5 1<=nums.length<=105
− 2 31 <=nums[i]<= 2 31 −1 -2^{31} <= nums[i] <= 2^{31} - 1 −231<=nums[i]<=231−1
0<=k<=1 0 5 0 <= k <= 10^5 0<=k<=105

进阶：

• 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
• 你可以使用空间复杂度为 $O(1)$ 的原地算法解决这个问题吗？

【分析】

通过观察很容易发现如果向右移动 $k$ 次就相当于将最后的 $k$ 个数放到数组最前面，如何用原地算法解决具有一定的跳跃性。

首先我们知道数组的翻转操作可以原地解决，因此可以想一下尝试用翻转操作处理这道题。解题思路为：首先翻转整个数组，此时最后 $k$ 个数已经在数组前面了，但是这 $k$ 个数包括其后面的 $n-k$ 个数还是逆序的，因此再分别翻转前 $k$ 个数和后 $n-k$ 个数即可。

模拟一下就很清晰了：

nums = [1, 2, 3, 4, 5, 6, 7], k = 31. 翻转整个数组：[7, 6, 5, 4, 3, 2, 1]2. 翻转前 k 个数：[5, 6, 7, 4, 3, 2, 1]3. 翻转后 n - k 个数：[5, 6, 7, 1, 2, 3, 4]

【代码】

class Solution {public: void rotate(vector<int>& nums, int k) { int n = nums.size(); k %= n; // 去除多余的循环位移 reverse(nums.begin(), nums.end()); reverse(nums.begin(), nums.begin() + k); reverse(nums.begin() + k, nums.end()); }};