DAY3 2026.03.15
LeetCode239 滑动窗口最大值 [单调队列、滑动窗口]
单调队列，Deque存放的是下标
- 队尾入，保持队列单调，老元素小于等于新元素则被弹出
- 队首出，队首元素小于left，则表明它已在窗口外，弹出
- 队首元素对应的nums中元素是当前窗口的最大值，left>=0的时候开始记录
LeetCode209 长度最小的子数组 [滑动窗口]
滑动窗口，关键在于确定什么时候该移动left指针，什么时候记录当前窗口长度
LeetCode76 最小覆盖子串 [滑动窗口]
滑动窗口，单独实现isCovered()方法来判断当前窗口内的字符串是否覆盖了目标串，即窗口内的目标字符数量是否大于等于目标串中对应的字符数量。解题思路与”LeetCode209 长度最小的子数组“相似，关键在于确定什么时候left往右移动，什么时候收割答案
在前面的基础上再进行优化，从O(52m+n)优化成O(m+n)。不用isCovered()判断覆盖，而是使用geCnt变量表示目前窗口的子串中有geCnt种字母的出现次数大于等于t中相应字母的出现次数
- 如果curChar加入窗口后，窗口子串的curChar与t的curChar一样多（diff[curChar] == 0），geCnt加一
- 如果outChar离开窗口前，窗口子串的outChar与t的outChar一样多(diff[outChar] == 0)，离开会小于，所以geCnt减一
LeetCode53 最大子数组和 [贪心、动态规划]
思路一：贪心，尽可能的让子数组和大，所以当curSum为负数时要立即抛弃，从下一个重新开始累加
思路二：动态规划，dp[i]表示以元素nums[i]为结尾的最大连续子序列的和，两种情况：
- 接着前面的值继续往下累加：dp[i] = dp[i-1] + nums[i]
- 重新开始累加：dp[i] = nums[i]
综合便有：dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
LeetCode56 合并区间 [数组]
先对数组按照区间左边界的大小升序排序，然后遍历。如果当前区间左边界小于等于合并区间的右边界，则合并进去；否则，记录合并区间，然后将当前区间作为新的合并区间。最后出循环后，还要再把最后一次的合并区间记录进去
LeetCode189 轮转数组 [数组]
思路一：另外设一个result数组。result[(i+k)%length] = nums[i]，将nums数组轮转后的元素存在result数组中，最后在用result数组覆盖nums数组即可
思路二：负负得正。要把[1,2,3,4,5,6,7]变成[5,6,7,1,2,3,4]，先把[5,6,7,1,2,3,4]看成[5,6,7] + [1,2,3,4]，首先保证[5,6,7]在[1,2,3,4]前面，这可以通过反转数组得到。反转后变成[7,6,5,4,3,2,1]，再分段单独反转就变成[5,6,7,1,2,3,4]