LeetCode 解题思路 6（Hot 100）
解题思路：
- 初始化窗口元素： 遍历前 k 个元素，构建初始单调队列。若当前索引对应值大于等于队尾索引对应值，移除队尾索引，将当前索引加入队尾。遍历结束时当前队头索引即为当前窗口最大值，将其存入结果数组。
- 处理剩余元素： 对于 k+1 之后的元素，加入规则同上。若队头索引已不在当前窗口范围内（即deque.peekFirst() <= i - k），则移除队头索引。当前队头索引即为窗口最大值，将其存入结果数组。
Java代码：
public class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;Deque<Integer> deque = new ArrayDeque<>();for (int i = 0; i < k; ++i) {while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {deque.pollLast();}deque.offerLast(i);} int[] res = new int[n - k + 1];res[0] = nums[deque.peekFirst()];for (int i = k; i < n; ++i) {while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {deque.pollLast();}deque.offerLast(i);if (deque.peekFirst() <= i - k) {deque.pollFirst();}res[i - k + 1] = nums[deque.peekFirst()];}return res;}
}
复杂度分析：
-
时间复杂度： O(n)，每个元素最多入队和出队一次，因此总操作次数为线性时间。
-
空间复杂度： O(k)，最坏情况下，队列中存储窗口内所有元素的索引（当数组严格递减时）。
解题思路：
- 字符统计初始化： 使用两个长度为 256 的数组 countT 和 countS，分别统计 t 中每个字符的出现次数，以及当前窗口中 s 的字符出现次数。
- 滑动窗口遍历： 右指针 r：遍历 s，将字符纳入窗口，并更新 countS。左指针 l：当窗口满足包含 t 所有字符的条件时，尽可能向右收缩窗口，以寻找更小的有效窗口。
- 窗口有效性判断： 通过 isInclude 方法检查当前窗口的字符是否覆盖了 t 的所有字符。
- 更新最小窗口： 每次找到有效窗口时，记录其长度和位置，最终返回最小的窗口子串。
Java代码：
class Solution {public String minWindow(String s, String t) {char[] S = s.toCharArray();char[] T = t.toCharArray();int n = S.length;int left = -1;int right = n;int[] countS = new int[128];int[] countT = new int[128];for (int i = 0; i < T.length; i++) {countT[T[i]]++;}int l = 0;for (int r = 0; r < n; r++) {countS[S[r]]++;while (isInclude(countS, countT)) {if (r - l < right - left) {right = r;left = l;}countS[S[l]]--;l++;}}return left < 0 ? "" : s.substring(left, right + 1);}public boolean isInclude(int[] countS, int[] countT) {for (int i = 0; i < 128; i++) {if (countS[i] < countT[i]) {return false;}}return true;}
}
复杂度分析：
- 时间复杂度： O(n)，左右指针移动最多 2n 次。
- 空间复杂度： O(1)，使用固定大小的数组，与输入规模无关。