LeetCode解题思路6（Hot100）

解题思路： 初始化窗口元素： 遍历前 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)，使用固定大小的数组，与输入规模无关。