LeetCode 1438. 绝对差不超过限制的最长连续子数组

2023-02-23 HGNULB 约 6 分钟

文章信息 8 个分类 6 个标签

分类

题目描述

✅ 1438. 绝对差不超过限制的最长连续子数组

题意分析

要找的是一段连续的子数组，它内部任意两个元素的绝对差都不超过 limit，问这样的子数组最长能有多长。「任意两数之差不超过 limit」这句话可以立刻化简：差值最大的一对必然是这段区间的最大值和最小值，所以条件等价于「区间最大值减区间最小值不超过 limit」，只需要盯住两个极值而不是所有数对。

「连续」这个词排除了排序和挑选，答案必须是原数组的一段区间；同时数组长度可以到 $10^5$，枚举所有区间是 $10^{10}$ 量级，必须找到只扫一遍的做法。

关键的单调性信号是：如果一段区间合法，那么它的任意子区间也一定合法，因为子区间的极值差不会更大。这意味着以某个右端点为终点的所有合法区间中，左端点的可行范围是一段连续后缀，而且这个最小可行左端点随右端点右移只会不减——这正是可以用两个指针单向推进的前提。

边界上要注意：limit 可以为 0，此时只有全部元素相等的区间合法；单个元素构成的区间极值差为 0，恒合法，所以答案至少是 1，永远不会返回 0；元素可能高达 $10^9$，两数相减仍在 int 范围内，但如果误用相加就要小心溢出。

解法：双单调队列滑动窗口

核心思路

一个窗口合法，当且仅当

窗口最大值 - 窗口最小值 <= limit。

合法窗口的任意子窗口仍合法，因此右端点向右移动时，左端点只需单调右移，适合滑动窗口。难点是窗口伸缩时快速得到最大值和最小值：

递减队列保存最大值候选，队首是窗口最大值；

递增队列保存最小值候选，队首是窗口最小值；

队列存下标，才能在左端点离开时判断元素是否过期。

新元素入队时，删除队尾所有不可能再成为极值的旧候选。例如递减队列中，若旧值不大于新值，新值更大且离开窗口更晚，旧值可永久淘汰。每个下标至多进入、离开每条队列一次。

循环不变量是：收缩结束后窗口 [left, right] 合法，两条队列的队首分别是该窗口的最大、最小值。于是每个右端点都能得到以它结尾的最长合法窗口。

解题步骤

右端点依次加入窗口，并维护递减的最大值队列和递增的最小值队列。

若两队首之差超过 limit，持续右移 left；离开的下标若位于队首，同步弹出。

窗口重新合法后，用 right - left + 1 更新答案。

以 [8,2,4,7]、limit = 4 为例：加入 2 后窗口 [8,2] 极差为 6，左端点移到 2；随后 [2,4] 合法、长度 2；加入 7 后 [2,4,7] 极差为 5，再移除 2，得到合法窗口 [4,7]，最长长度为 2。

代码实现

import java.util.ArrayDeque;
import java.util.Deque;

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)$，两条队列最坏都可能保存线性数量的下标。

关键点总结

极差约束可拆成窗口最大值与最小值，两条单调队列分别维护。

队列存下标而不是值，因为只有下标能判断候选是否已经离开窗口。

入队时从队尾淘汰较差候选，出窗口时只检查队首是否等于左端点。

收缩必须使用 while，一次右移未必足以恢复合法性。

替代方案是有序多重集，复杂度为 $O(n log n)$；固定值域不存在时，双端队列是更优的线性解。

易错点总结

最大、最小队列的单调方向写反：队首不再代表窗口极值。

队列只存值：重复值存在时无法判断离开的究竟是哪一个位置。

非法窗口只收缩一次：窗口可能仍然超限，却被用于更新答案。

左端点移动后无条件弹队首：队首元素可能仍在窗口内。

只比较新元素与某个极值：合法性取决于整个窗口的最大值减最小值。

相似题目

题目	难度	考察点
239. 滑动窗口最大值	困难	窗口长度固定，只需一条单调队列且无需收缩逻辑
3. 无重复字符的最长子串	中等	合法性由计数表判定，不涉及极值维护
904. 水果成篮	中等	约束是窗口内不同元素种类数不超过 2
1004. 最大连续1的个数 III	中等	约束是窗口内 0 的个数不超过 k，累加即可判定
209. 长度最小的子数组	中等	求最短窗口，靠前缀和的单调性而非极值
862. 和至少为 K 的最短子数组	困难	有负数导致窗口失效，需在前缀和上用单调队列