LeetCodeHot100_0x02
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;
}
}
【双端队列】优化获取最大值
- 入队原则：
- 时刻确保队首----队尾具有单调递减性
- 新元素入队时，从队尾开始比较，只要是小于等于的新元素的，没有机会成为最大值，我们可以直接将它出队列，然后将当前元素下标加入到队列的队尾
- 判断最大值是否还在窗口内，从队首开始，不断比较队首元素的下标和新加入元素下标的差是否比窗口长度大了，大了就把它出队列。
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-51
if(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; // 开头不是目标子串的字符,直接pass
int[] 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();
// 初始化Tcnt
for(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;
}
}
// 解法1
public 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;
}
// 解法2
public 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，以及一些字符串的方法和处理手段。不断刷题，巩固起来！