LeetCode 1438. 绝对差不超过限制的最长连续子数组
题目描述
题意分析
在所有连续子数组中，找到任意两个元素的绝对差都不超过
limit的最长长度。区间中最大的绝对差一定来自最大值与最小值，因此合法条件等价于max - min <= limit，不需要逐对比较。向右加入元素时，区间极差不会减小；从左侧移出元素时，极差不会增大。这种单调性允许用滑动窗口维护合法区间，难点是快速得到窗口的最大值与最小值。
解法：双单调队列滑动窗口
核心思路
[!blue]
维护窗口
[left, right]，再用两条存放下标的双端队列记录极值候选。两条队列的下标都从头到尾递增，最大值队列对应的数值递减，最小值队列对应的数值递增，因此两个队首就是当前窗口的最大值与最小值。右端加入新元素时，最大值队列从尾部删除所有不大于新值的候选。旧候选位置更早、值又不更大：以后只要窗口还包含它，就一定也包含新元素，而新元素更有资格成为最大值、离开窗口也更晚，所以旧候选可以永久淘汰。最小值队列对称地删除不小于新值的队尾。
加入右端后，若两个队首的差大于
limit，就持续右移left。移出的下标只有恰好位于队首时才需要弹出。若它不在某条队列的队首，说明它已经从这条队列中被淘汰，无需额外处理，不能把仍在窗口中的队首误删。第一次恢复合法时停止收缩，此时得到以
right结尾的最长合法窗口。更靠左的起点已经证明会超限；之后继续扩大右端也不能让这些起点重新合法，所以左指针只需向右移动。依次取各个右端的最长长度，就得到全局答案。题目保证
limit >= 0，单个元素的极差为0，因此收缩最迟会在单元素窗口停止，不会把窗口缩空。
解题步骤
- 初始化两条空队列、左边界
left = 0和答案answer = 0。- 每次扩展
right，弹出最大值队列中不大于新值的队尾，以及最小值队列中不小于新值的队尾，再把right加入两条队列。- 比较两个队首对应的值。若极差超限，检查
left是否位于任一队首，是则弹出，再让left加一，重复直到窗口合法。- 用
right - left + 1更新答案，再处理下一个右端。- Go 用切片和
maxHead、minHead模拟队列。有效元素从头下标开始，队尾弹出条件也必须限制在这个有效范围内。
代码实现
class Solution {
public int longestSubarray(int[] nums, int limit) {
Deque<Integer> maxQueue = new ArrayDeque<>();
Deque<Integer> minQueue = new ArrayDeque<>();
int left = 0;
int answer = 0;
for (int right = 0; right < nums.length; right++) {
// 更新且不更小的新值支配旧候选，可从尾部永久淘汰
while (!maxQueue.isEmpty() && nums[maxQueue.peekLast()] <= nums[right]) {
maxQueue.pollLast();
}
while (!minQueue.isEmpty() && nums[minQueue.peekLast()] >= nums[right]) {
minQueue.pollLast();
}
maxQueue.offerLast(right);
minQueue.offerLast(right);
// 持续收缩到极差合法，只移除实际过期的队首
while (nums[maxQueue.peekFirst()] - nums[minQueue.peekFirst()] > limit) {
// 移出的是当前左端，检查并清理对应队首后再前移
if (maxQueue.peekFirst() == left) {
maxQueue.pollFirst();
}
if (minQueue.peekFirst() == left) {
minQueue.pollFirst();
}
left++;
}
answer = Math.max(answer, right - left + 1);
}
return answer;
}
}
func longestSubarray(nums []int, limit int) int {
maxQueue := make([]int, 0, len(nums))
minQueue := make([]int, 0, len(nums))
maxHead, minHead := 0, 0
left, answer := 0, 0
for right, num := range nums {
// 更新且不更小的新值支配旧候选，可从尾部永久淘汰
for len(maxQueue) > maxHead &&
nums[maxQueue[len(maxQueue)-1]] <= num {
maxQueue = maxQueue[:len(maxQueue)-1]
}
for len(minQueue) > minHead &&
nums[minQueue[len(minQueue)-1]] >= num {
minQueue = minQueue[:len(minQueue)-1]
}
maxQueue = append(maxQueue, right)
minQueue = append(minQueue, right)
// 持续收缩到极差合法，只移除实际过期的队首
for nums[maxQueue[maxHead]]-nums[minQueue[minHead]] > limit {
// 移出的是当前左端，检查并清理对应队首后再前移
if maxQueue[maxHead] == left {
maxHead++
}
if minQueue[minHead] == left {
minHead++
}
left++
}
if right-left+1 > answer {
answer = right - left + 1
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n)$，每个下标在每条队列中进出至多一次。
- 空间复杂度：$O(n)$，两条候选队列。
关键点总结
[!green]
- 极差代替任意两元素的比较，双单调队列让两个极值始终位于队首。
- 从队尾删除的是被新元素替代的候选，从队首删除的是已经离开窗口的下标，两种操作理由不同。
- 每个下标在每条队列中只会加入一次、删除至多一次，所以多重循环仍是线性总时间。
- 左端只收缩到首次合法，才能保留当前右端下的最大长度。
易错点总结
[!yellow]
- 最大值队列按值递减，最小值队列按值递增，不要把两个方向写反。
- 队列保存下标，才能准确判断哪个候选离开了窗口；仅凭数值无法区分重复元素的位置。
- 左边界移动时，只有队首下标等于旧
left才弹出，不能每次无条件弹队首。- 一次移动未必能消除超限，需要使用循环；恢复合法之前不能更新答案。
- Go 的队尾操作不能越过
maxHead或minHead，头下标之前的区域已经不属于有效队列。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 239. 滑动窗口最大值 | 困难 | 一个单调队列维护最大值，再增加一个维护最小值，窗口合法性由两者差决定。 |
| 862. 和至少为 K 的最短子数组 | 困难 | 用单调队列删除过期且不可能更优的候选；本题同时维护窗口最大值和最小值，该题按前缀和维护可能的最短区间起点。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！