目录239. 滑动窗口最大值题目描述解题思路满分代码自定义单调队列核心亮点76. 最小覆盖子串Hard题目描述解题思路满分代码极简注释版核心关键点刷题总结这两道题是算法面试必考的滑动窗口体系核心题一道是单调队列的经典应用滑动窗口最大值一道是滑动窗口 哈希表的 Hard 级天花板最小覆盖子串。我用最通俗的思路拆解 满分注释代码新手也能直接看懂、上手就写239. 滑动窗口最大值题目描述给定一个数组nums和一个滑动窗口大小k从数组最左侧移动到最右侧每次窗口移动一位返回每个窗口内的最大值。解题思路暴力解法会遍历所有窗口时间复杂度 O(n∗k) 直接超时。最优解自定义单调递减队列 **核心思想维护一个双端队列保证队列从队头到队尾单调递减队首永远是当前窗口的最大值入队新元素入队时移除所有比它小的队尾元素小元素不可能成为最大值直接舍弃出队窗口滑动时若要移除的元素恰好是队首最大值才将其出队每个窗口直接取队首元素就是当前窗口最大值。满分代码自定义单调队列java运行/** * 自定义单调递减队列 * 核心保证队首元素永远是当前窗口的最大值 */ class MyDeque { DequeInteger deque new LinkedList(); // 出队操作只有要移除的元素是队首最大值时才弹出 void poll(int val) { if (!deque.isEmpty() val deque.peek()) { deque.poll(); } } // 入队操作移除所有比当前元素小的尾部元素保证队列单调递减 void add(int val) { while (!deque.isEmpty() val deque.getLast()) { deque.removeLast(); } deque.add(val); } // 获取当前窗口最大值队首元素 int peek() { return deque.peek(); } } class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; // 结果数组长度n - k 1 int[] res new int[n - k 1]; int index 0; MyDeque myDeque new MyDeque(); // 1. 先初始化第一个窗口的元素 for (int i 0; i k; i) { myDeque.add(nums[i]); } // 记录第一个窗口的最大值 res[index] myDeque.peek(); // 2. 滑动窗口遍历后续元素 for (int i k; i n; i) { // 窗口右移移除窗口最左侧的元素 myDeque.poll(nums[i - k]); // 加入窗口新元素 myDeque.add(nums[i]); // 记录当前窗口最大值 res[index] myDeque.peek(); } return res; } }核心亮点时间复杂度O(n)每个元素仅入队、出队一次空间复杂度O(k)队列最多存储 k 个元素面试必背单调队列专门解决滑动窗口极值问题76. 最小覆盖子串Hard题目描述给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串如果不存在返回空字符串。解题思路这是滑动窗口的天花板题目核心套路双指针 双哈希表 精准计数用两个哈希表need记录目标字符串 t 的字符需求window记录当前窗口内的字符右指针不断右移扩大窗口直到窗口包含 t 所有字符左指针开始收缩窗口尽可能缩小长度同时更新最小子串用strnumber记录窗口内完全匹配的字符种类数精准控制窗口收缩时机。满分代码极简注释版java运行class Solution { public String minWindow(String s, String t) { // 边界特判 if (s null || t null || s.isEmpty() || t.isEmpty()) { return ; } // need记录目标字符串t的字符及数量 MapCharacter, Integer need new HashMap(); // window记录当前滑动窗口内的字符及数量 MapCharacter, Integer window new HashMap(); // 滑动窗口左右指针 int left 0, right 0; // 窗口内已匹配的字符种类数和need完全匹配的数量 int matchCount 0; // 记录最小子串的长度和起始索引 int minLen Integer.MAX_VALUE; int start 0; // 初始化need哈希表 for (char c : t.toCharArray()) { need.put(c, need.getOrDefault(c, 0) 1); } // 右指针扩大窗口 while (right s.length()) { char rightChar s.charAt(right); right; // 更新窗口内字符计数 if (need.containsKey(rightChar)) { window.put(rightChar, window.getOrDefault(rightChar, 0) 1); // 当前字符数量完全匹配匹配数1 if (window.get(rightChar).equals(need.get(rightChar))) { matchCount; } } // 窗口已包含所有t的字符开始收缩左指针优化最小长度 while (matchCount need.size()) { // 更新最小子串 if (right - left minLen) { start left; minLen right - left; } // 左指针右移缩小窗口 char leftChar s.charAt(left); if (window.containsKey(leftChar)) { window.put(leftChar, window.get(leftChar) - 1); // 字符数量不匹配匹配数-1 if (window.get(leftChar) need.get(leftChar)) { matchCount--; } } left; } } // 没有找到合法子串返回空否则返回最小子串 return minLen Integer.MAX_VALUE ? : s.substring(start, start minLen); } }核心关键点双哈希表解耦严格区分目标字符和窗口字符避免计数混乱matchCount 精准控制只有字符数量完全相等时才计数是收缩窗口的唯一依据收缩窗口优化找到合法窗口后尽可能缩小保证得到最小子串。刷题总结滑动窗口最大值单调队列专属场景解决滑动窗口极值问题队首恒为最值最小覆盖子串滑动窗口 哈希表经典 Hard 题掌握「扩大窗口→匹配→收缩窗口」模板同类题一通百通
算法高频压轴题｜滑动窗口最大值 + 最小覆盖子串，单调队列 + 滑动窗口双杀
目录239. 滑动窗口最大值题目描述解题思路满分代码自定义单调队列核心亮点76. 最小覆盖子串Hard题目描述解题思路满分代码极简注释版核心关键点刷题总结这两道题是算法面试必考的滑动窗口体系核心题一道是单调队列的经典应用滑动窗口最大值一道是滑动窗口 哈希表的 Hard 级天花板最小覆盖子串。我用最通俗的思路拆解 满分注释代码新手也能直接看懂、上手就写239. 滑动窗口最大值题目描述给定一个数组nums和一个滑动窗口大小k从数组最左侧移动到最右侧每次窗口移动一位返回每个窗口内的最大值。解题思路暴力解法会遍历所有窗口时间复杂度 O(n∗k) 直接超时。最优解自定义单调递减队列 **核心思想维护一个双端队列保证队列从队头到队尾单调递减队首永远是当前窗口的最大值入队新元素入队时移除所有比它小的队尾元素小元素不可能成为最大值直接舍弃出队窗口滑动时若要移除的元素恰好是队首最大值才将其出队每个窗口直接取队首元素就是当前窗口最大值。满分代码自定义单调队列java运行/** * 自定义单调递减队列 * 核心保证队首元素永远是当前窗口的最大值 */ class MyDeque { DequeInteger deque new LinkedList(); // 出队操作只有要移除的元素是队首最大值时才弹出 void poll(int val) { if (!deque.isEmpty() val deque.peek()) { deque.poll(); } } // 入队操作移除所有比当前元素小的尾部元素保证队列单调递减 void add(int val) { while (!deque.isEmpty() val deque.getLast()) { deque.removeLast(); } deque.add(val); } // 获取当前窗口最大值队首元素 int peek() { return deque.peek(); } } class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; // 结果数组长度n - k 1 int[] res new int[n - k 1]; int index 0; MyDeque myDeque new MyDeque(); // 1. 先初始化第一个窗口的元素 for (int i 0; i k; i) { myDeque.add(nums[i]); } // 记录第一个窗口的最大值 res[index] myDeque.peek(); // 2. 滑动窗口遍历后续元素 for (int i k; i n; i) { // 窗口右移移除窗口最左侧的元素 myDeque.poll(nums[i - k]); // 加入窗口新元素 myDeque.add(nums[i]); // 记录当前窗口最大值 res[index] myDeque.peek(); } return res; } }核心亮点时间复杂度O(n)每个元素仅入队、出队一次空间复杂度O(k)队列最多存储 k 个元素面试必背单调队列专门解决滑动窗口极值问题76. 最小覆盖子串Hard题目描述给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串如果不存在返回空字符串。解题思路这是滑动窗口的天花板题目核心套路双指针 双哈希表 精准计数用两个哈希表need记录目标字符串 t 的字符需求window记录当前窗口内的字符右指针不断右移扩大窗口直到窗口包含 t 所有字符左指针开始收缩窗口尽可能缩小长度同时更新最小子串用strnumber记录窗口内完全匹配的字符种类数精准控制窗口收缩时机。满分代码极简注释版java运行class Solution { public String minWindow(String s, String t) { // 边界特判 if (s null || t null || s.isEmpty() || t.isEmpty()) { return ; } // need记录目标字符串t的字符及数量 MapCharacter, Integer need new HashMap(); // window记录当前滑动窗口内的字符及数量 MapCharacter, Integer window new HashMap(); // 滑动窗口左右指针 int left 0, right 0; // 窗口内已匹配的字符种类数和need完全匹配的数量 int matchCount 0; // 记录最小子串的长度和起始索引 int minLen Integer.MAX_VALUE; int start 0; // 初始化need哈希表 for (char c : t.toCharArray()) { need.put(c, need.getOrDefault(c, 0) 1); } // 右指针扩大窗口 while (right s.length()) { char rightChar s.charAt(right); right; // 更新窗口内字符计数 if (need.containsKey(rightChar)) { window.put(rightChar, window.getOrDefault(rightChar, 0) 1); // 当前字符数量完全匹配匹配数1 if (window.get(rightChar).equals(need.get(rightChar))) { matchCount; } } // 窗口已包含所有t的字符开始收缩左指针优化最小长度 while (matchCount need.size()) { // 更新最小子串 if (right - left minLen) { start left; minLen right - left; } // 左指针右移缩小窗口 char leftChar s.charAt(left); if (window.containsKey(leftChar)) { window.put(leftChar, window.get(leftChar) - 1); // 字符数量不匹配匹配数-1 if (window.get(leftChar) need.get(leftChar)) { matchCount--; } } left; } } // 没有找到合法子串返回空否则返回最小子串 return minLen Integer.MAX_VALUE ? : s.substring(start, start minLen); } }核心关键点双哈希表解耦严格区分目标字符和窗口字符避免计数混乱matchCount 精准控制只有字符数量完全相等时才计数是收缩窗口的唯一依据收缩窗口优化找到合法窗口后尽可能缩小保证得到最小子串。刷题总结滑动窗口最大值单调队列专属场景解决滑动窗口极值问题队首恒为最值最小覆盖子串滑动窗口 哈希表经典 Hard 题掌握「扩大窗口→匹配→收缩窗口」模板同类题一通百通
