1438. 绝对差不超过限制的最长连续子数组：「单调队列」，或「自平衡 BST 红黑树 TreeSet」维护滑动窗口最值.md

题目简述：

给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit。

题目链接：1438. 绝对差不超过限制的最长连续子数组

TreeSet 红黑树维护子数组最值

思路

该问题是很显然的滑动窗口问题，令人困惑的点在于如何高效维护子数组的最大绝对差。如果滑动窗口每次更新后都遍历滑动窗口内的子数组以获取子数组的最大值和最小值，时间复杂度将来到 $O(n^2)$，这不可接受。

要维护区间最值，优先队列 / 大小顶堆或许是最合适的数据结构之一，但问题在于优先队列 / 大小顶堆似乎不太能高效地淘汰已经过期的、处于滑动窗口左边界外的元素，详情参见我的题解 480. 滑动窗口中位数：双堆维护中位数，但是需要高效实现过期策略，因此使用红黑树 TreeSet 而不考虑优先队列 PriorityQueue.md。一个简单、暴力但有效的方案是用红黑树的实现 TreeSet 维护滑动窗口内子数组的最值。

作为一种自平衡的 BST，TreeSet 维护了最左节点与最右节点，因此获取最大值与最小值的时间开销为 $O(1)$，更新一个节点的时间开销为 $O(\log n)$。虽然效率并不算很高，但至少是可行的。

代码

算法的时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。

record Pair(int index, int val) implements Comparable<Pair> {
    @Override
    public int compareTo(Pair o) {
        int compared = Integer.compare(this.val, o.val);
        if (compared != 0) return compared;
        return Integer.compare(this.index, o.index);
    }
}

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        int n = nums.length;
        int res = 0;
        TreeSet<Pair> tree = new TreeSet<>();

        int l = 0;
        for (int r = 0; r < n; r++) {
            tree.add(new Pair(r, nums[r]));
            while (l < r && tree.last().val() - tree.first().val() > limit) {
                tree.remove(new Pair(l, nums[l]));
                l++;
            }
            res = Math.max(res, r - l + 1);
        }

        return res;
    }
}

单调队列

思路

还记得在 239. 滑动窗口最大值 的题解中我有说过，计算滑动窗口的最值是单调队列最典型的模板应用吗？单调队列不像单调栈所解决的 NGE & PGE 问题有那么广泛的应用场景，但针对滑动窗口的最值这一特化问题，没有比单调队列更适合的数据结构了，单调队列能够以平均 $O(1)$ 的时间复杂度得到滑动窗口内的最值。

以维护滑动窗口的最大值为例，我们对 nums 内的每个元素封装索引与值，其中封装索引是为了实现过期淘汰动作，封装值是为了维护队列内的单调性。然后，我们维护队列内自队尾至队首单调递增：

• 滑动窗口的右边界扩张后（扫描到一个新的元素后），尝试在维护队列内单调递增的前提下将其封装后的对象插入到队列尾部，如果当前队尾封装对象的值比新对象的值更小，则（从队尾）弹出当前队尾，循环操作直到能够顺利让新对象入队；
• 滑动窗口的左边界收缩后，检查队首的若干对象是否过期，如果过期则（从队首）弹出对象。

这样就能以 $O(1)$ 的时间复杂度得到滑动窗口的最大值。维护滑动窗口的最小值同理。

代码

算法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

record Pair(int index, int val) {}

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        int n = nums.length;
        int res = 0;
        Deque<Pair> maxQueue = new ArrayDeque<>();
        Deque<Pair> minQueue = new ArrayDeque<>();

        int l = 0;
        for (int r = 0; r < n; r++) {
            while (!maxQueue.isEmpty() && maxQueue.peekLast().val() < nums[r]) {
                maxQueue.removeLast();
            }
            maxQueue.addLast(new Pair(r, nums[r]));

            while (!minQueue.isEmpty() && minQueue.peekLast().val() > nums[r]) {
                minQueue.removeLast();
            }
            minQueue.addLast(new Pair(r, nums[r]));
            
            while (l < r && maxQueue.peekFirst().val() - minQueue.peekFirst().val() > limit) {
                l++;
                if (maxQueue.peekFirst().index() < l) maxQueue.removeFirst();
                if (minQueue.peekFirst().index() < l) minQueue.removeFirst();
            }
            res = Math.max(res, r - l + 1);
        }

        return res;
    }
}