当前位置：首页 > news >正文

LeetCodeHot100_0x02

news 来源：原创 2025/9/15 11:05:45

LeetCodeHot100_0x02

11. 滑动窗口最大值（不熟）

求解思路： 暴力法的时间复杂度是O(NK)，在K常数较大时复杂度就高了。所以我们要想办法将K优化掉，即本题的难点在于如何在O(1)的时间复杂度求出当前窗口中的最大值。这个特性会让我们想到 优先队列、双端队列。但是什么是正确的入队规则，这里我独自想不出来。在理解题解过后，也能独自完成代码的编写了。
【暴力法】超出时间限制 40 / 51 个通过的测试用例

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {// 暴力法int n = nums.length;int[] res = new int[n-k+1];for(int i=0;i<n-k+1;i++) {int maxN = nums[i];for(int j=i;j<i+k;j++) {if(nums[j] > maxN) maxN = nums[j];}res[i] = maxN;}return res;}
}

【双端队列】优化获取最大值

入队原则：
1. 时刻确保队首----队尾具有单调递减性
2. 新元素入队时，从队尾开始比较，只要是小于等于的新元素的，没有机会成为最大值，我们可以直接将它出队列，然后将当前元素下标加入到队列的队尾
3. 判断最大值是否还在窗口内，从队首开始，不断比较队首元素的下标和新加入元素下标的差是否比窗口长度大了，大了就把它出队列。

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {/**本题难点在于O(1)内获得窗口的最大值（思考数据结构：单调栈、堆）窗口的结构就和：双端队列是一样的利用双端队列完成这题：如何保证队列的单调性？1. 队头存储最大值，逐步递减2. 新元素入队时，从队尾开始逐个比较，比其小的全部淘汰【能力不如,年龄也不如,没机会】3. 队头元素如果离开了窗口范围，也淘汰掉【年龄大了，退休】如何确定队头元素离开了窗口范围呢？可以用队列存储下标信息，与当前新加入元素下标对比即可*/int n = nums.length;int[] res = new int[n-k+1];// 这个是双端队列的定义，存储元素下标Deque<Integer> dqIdx = new LinkedList<>();for(int i=0;i<k;i++) {// 新元素入队，从队尾逐个比较，把“又弱又老”的元素给删除【两步动作，先比较，后入队】//1. 比较(如果队列为空就不用比较了)while(!dqIdx.isEmpty() && nums[i] >= nums[dqIdx.getLast()]) dqIdx.removeLast();//2. 新元素入队dqIdx.addLast(i);}res[0] = nums[dqIdx.getFirst()];  // 第一个窗口的最大值出来了for(int i=k;i<n;i++) {// 新元素入队，从队尾逐个比较，把“又弱又老”的元素给删除【两步动作，先比较，后入队】//1. 比较(如果队列为空就不用比较了)while(!dqIdx.isEmpty() && nums[i] >= nums[dqIdx.getLast()]) dqIdx.removeLast();//2. 新元素入队dqIdx.addLast(i);//3. 判断最大值有没有超出窗口【下标是否大于k】while(i - dqIdx.getFirst() >= k) dqIdx.removeFirst();//4. 当前窗口的最大值res[i-k+1] = nums[dqIdx.getFirst()];}return res;}
}

复习： 双端队列Deque的用法

Java中的Deque（双端队列）是一种支持在队列两端插入和删除元素的数据结构。它既可用作先进先出（FIFO）的队列，也可用作后进先出（LIFO）的栈。以下是其核心用法和常用方法的详细介绍：

1. Deque 概述

接口定义：java.util.Deque，继承自Queue接口。
核心特性：允许在队头和队尾高效插入、删除和查看元素。
实现类：
- ArrayDeque：基于动态数组实现，性能高效，推荐大多数场景使用。
- LinkedList：基于链表实现，支持快速两端操作，同时实现了List接口。
用途：
- 替代Stack类（官方推荐使用Deque实现栈，因Stack是同步的且设计老旧）。
- 实现普通队列、双端队列或循环队列。

2. 常用方法
Deque的方法分为两类：操作失败时抛出异常或返回特殊值（如null/false）。

操作	抛出异常的方法	返回特殊值的方法
插入队头	`addFirst(e)`	`offerFirst(e)`
插入队尾	`addLast(e)`	`offerLast(e)`
移除队头	`removeFirst()`	`pollFirst()`
移除队尾	`removeLast()`	`pollLast()`
查看队头	`getFirst()`	`peekFirst()`
查看队尾	`getLast()`	`peekLast()`

队列操作（FIFO）

入队：add(e)（等价于addLast(e)）或 offer(e)（等价于offerLast(e)）。
出队：remove()（等价于removeFirst()）或 poll()（等价于pollFirst()）。
查看队头：element()（等价于getFirst()）或 peek()（等价于peekFirst()）。

栈操作（LIFO）

入栈：push(e)（等价于addFirst(e)）。
出栈：pop()（等价于removeFirst()）。
查看栈顶：peek()（等价于peekFirst()）。

3. 实现类选择

ArrayDeque：
- 默认选择，内存连续，访问高效。
- 初始容量为16，自动扩容，适合大多数场景。
LinkedList：
- 支持List操作，可在中间插入/删除（但性能较差）。
- 每个元素需额外内存存储节点，适合频繁的两端操作。

4. 示例代码
作为栈使用

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);      // 栈顶插入
stack.push(2);
int top = stack.pop();  // 返回2（栈顶元素）

作为队列使用

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);     // 队尾插入
queue.offer(2);
int first = queue.poll(); // 返回1（队头元素）

双端操作

Deque<String> deque = new LinkedList<>();
deque.offerFirst("A");  // 队头插入
deque.offerLast("B");   // 队尾插入
String head = deque.pollFirst(); // "A"
String tail = deque.pollLast();  // "B"

5. 注意事项

线程安全：ArrayDeque和LinkedList非线程安全，多线程环境下需使用Collections.synchronizedDeque或并发容器。
空值处理：LinkedList允许插入null，而ArrayDeque会抛出NullPointerException。
性能考量：频繁的随机访问选择ArrayDeque，频繁插入删除两端且需灵活性时选择LinkedList。

12. 最小覆盖子串（不会）

求解思路： 尝试使用哈希法进行求解，最后写出来超时了，证明单纯的双循环还是不能解决问题，需要思考如何进行优化。
【暴力哈希法】超出时间限制 265 / 268 个通过的测试用例
这段代码写的比较冗杂，比如判断大小写可以抽取、当前长度currlen可有可无，不过超时代码就不改了。就当是记录做题的一个草稿过程。

class Solution {public String minWindow(String s, String t) {/** 哈希模拟选择过程两层循环，第一层循环枚举符合的子串开头包含目标子串的字符才能作为开头，否则不可能最优（因为一定能存在更短的）第二层循环开始消耗目标子串值（哈希），直到匹配成功，判断当前长度*/int n = s.length();int m = t.length();int[] Tcnt = new int[52]; // 大写字母0-25，小写字母26-51if(m > n) return "";// 进行统计int minLen = n + m;String res = "";for(int i=0;i<m;i++) {if(t.charAt(i) >='A' && t.charAt(i) <='Z') {Tcnt[t.charAt(i)-'A'] ++;}else{Tcnt[t.charAt(i)-'a'+26] ++;} }for(int i=0;i<n;i++) {int p = 0;    // 当前字母(子串的开始)对应的哈希下标int cnt = m;  // 当前需要匹配的字符数（为0证明该子串包含了目标子串）int currLen = 0; // 当前子串长度if(s.charAt(i)>='A' && s.charAt(i)<='Z'){p = s.charAt(i)-'A'; }else {p = s.charAt(i)-'a' + 26;}if(Tcnt[p]<=0) continue; // 开头不是目标子串的字符,直接passint[] CopyT = (int[])Arrays.copyOf(Tcnt,52); // 复制原数组for(int j=i;j<n;j++) { // 从当前字母开始currLen++;  int k = 0;   // 当前枚举到的字符if(s.charAt(j)>='A' && s.charAt(j)<='Z'){k = s.charAt(j)-'A';}else {k = s.charAt(j)-'a' + 26;}if(CopyT[k] > 0) {  // 如果是目标子串，认为是有效的CopyT[k] --;cnt-=1;}if(cnt==0 && minLen > currLen) { res = s.substring(i,j+1);minLen = currLen;}}}return res;}
}

【滑动窗口法】仍然是使用哈希存储字符组成，然后利用双指针维护窗口，先向右扩展，直到窗口内字符包含目标子串，接着向右缩小窗口，直到长度最小可满足的位置，记录这个时候的是否需要更新答案，循环下去即可。滑动窗口相比上面的暴力法，减少了很多重复枚举，因此可以通过，但特别抽象。我暂时只是看题解理解了，但是还是很难写出来。

class Solution {public String minWindow(String s, String t) {//1. 边界值处理if (s == null || s.isEmpty() || t == null || t.isEmpty() || s.length() < t.length()) return "";// 定义哈希表，记录字符组成Map<Character, Integer> Tcnt = new HashMap<>();Map<Character, Integer> Scnt = new HashMap<>();int n = s.length();int m = t.length();// 初始化Tcntfor(int i=0;i<m;i++) {char c = t.charAt(i);Tcnt.put(c,Tcnt.getOrDefault(c,0) + 1);}int left = 0, right = 0; // 窗口指针int cnt = 0; // 已经匹配上的字符数量int start = 0, minLen = n + m; // 最小窗口的起始位置和当前最短符合条件的子串长度// 开始while (right < s.length()) {//1. 向右扩展窗口char r = s.charAt(right);right++;// 更新if (Tcnt.containsKey(r)) { // 如果这个字符存在于Tcnt中，我们人为是有效的Scnt.put(r, Scnt.getOrDefault(r, 0) + 1); if (Scnt.get(r).equals(Tcnt.get(r))) cnt++;}//2. 向右减小窗口while (cnt == Tcnt.size()) {// 更新起始位置和长度if (right - left < minLen) {start = left;minLen = right - left;}// 获取字符char l = s.charAt(left);// 缩小窗口，移动左边界if (Tcnt.containsKey(l)) {Scnt.put(l, Scnt.get(l) - 1);if (Scnt.get(l) < Tcnt.get(l)) cnt--;}left++; // 继续缩小}}return minLen == n+m ? "" : s.substring(start, start + minLen);}}

13. 最大子数组和

求解思路： 这题要搞懂一个问题就行：正负抵消
我们在遍历的过程中，有正有负，只要当前连续和为正，那么这段连续和就还有意义。而如果出现了连续和为负的情况，说明前面这段完全没有价值了，何不重新开始。在这个过程中，不断记录遇到的连续和，其中的最大值就是答案。这个过程有点类似贪心（安逸版）
【贪心】

class Solution {public int maxSubArray(int[] nums) {// 动态规划int n = nums.length;int sum = 0;int res = -10000;for(int i=0;i<n;i++) {sum += nums[i]; res = Math.max(res,sum); // 更新最大值if(sum < 0) {sum = 0; // 发现贡献抵消，那么这里就没必要继续下去了，重来}}return res;}
}

14. 合并区间

求解思路： 这题就是区间合并模板题了，所谓区间合并，解题有两步骤：

对区间按照x坐标从小到大进行排序
遍历区间，用链表动态维护 rk. y 与 rk+1.x 【前一y坐标与后一x坐标大小关系】

【区间合并模板】

class Solution {public int[][] merge(int[][] intervals) {// 区间合并模板//1. 边界判断if (intervals.length == 0) return new int[0][];// 2. 按区间起始位置排序 （Lambda表达式）Arrays.sort(intervals, (a, b) -> a[0] - b[0]);LinkedList<int[]> res = new LinkedList<>();for (int[] interval : intervals) {// 3. 合并逻辑：比较最后一个区间的结束位置if (!res.isEmpty() && res.getLast()[1] >= interval[0]) {// 如果可以合并，那就更新y坐标的值（两者最大值） res.getLast()[1] = Math.max(res.getLast()[1], interval[1]);} else {// 如果不可以合并，那就是新区间，写入res.add(interval);}}// 4. 转换为数组返回return res.toArray(new int[res.size()][]);}
}

15. 轮转数组

求解思路： 辅助数组、翻转思想
【辅助数组、翻转】

class Solution {public void rotate(int[] nums, int k) {// 方法1：辅助数组// int[] res = solve1(nums,k);// 方法2：整体局部翻转int[] res = solve2(nums,k);for(int i=0;i<nums.length;i++) {nums[i] = res[i];}  }// 翻转函数private void reverse(int[] nums, int start, int end) {while (start < end) {int temp = nums[start];nums[start] = nums[end];nums[end] = temp;start += 1;end -= 1;}}// 解法1public int[] solve1(int[] nums,int k) {int[] res = new int[nums.length];k = k % nums.length;// 遍历原数组for(int i=0;i<nums.length;i++) {int j = (i + k) % nums.length;res[j] = nums[i];}return res;}// 解法2public int[] solve2(int[] nums,int k) {k = k % nums.length;// 整体翻转reverse(nums,0,nums.length-1);// 两个局部分别翻转reverse(nums,0,k-1);reverse(nums,k,nums.length-1);return nums;}
}

16. 除自身以外的数组的乘积

**求解思路：**除自身之外的数组的乘积，可以分割为当前元素前缀乘与后缀乘的乘积。
为什么要提前计算这两个乘积呢，其实就是空间换时间的体现啦。
【前缀预处理思想法】

class Solution {public int[] productExceptSelf(int[] nums) {// 前缀乘、后缀乘int n = nums.length;int[] ln = new int[n];int[] rn = new int[n];ln[0] = 1;for(int i=1;i<n;i++) {ln[i] = nums[i-1] * ln[i-1];}rn[n-1] = 1;for(int i=n-2;i>=0;i--) {rn[i] = rn[i+1] * nums[i+1];}int[] res = new int[nums.length];for(int i=0;i<n;i++) {res[i] = ln[i] * rn[i];}return res;}
}

17. 今日总结

今天刷题量相比昨天少一些，主要是遇到太多特别难缠的题目了。今天最大的收获就是滑动窗口思想，滑动窗口主要解决动态连续区间内的最值、符合某种条件的组合值等问题。其他的还有像动态规划、前缀和思想、区间合并思想。

另外，今天在刷题的过程中还是遇到了很多问题，特别是对于一些陌生的数据结构例如Deque、LinkList，以及一些字符串的方法和处理手段。不断刷题，巩固起来！