各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 28 天。今天力扣上的每日一题是「1438. 绝对差不超过限制的最长连续子数组」。

解题思路

• 题意：求一个最长的子数组，该子数组内的最大值和最小值的差不超过 $limit$。

本题是求最大连续子区间，可以使用滑动窗口方法。滑动窗口的限制条件是：窗口内最大值和最小值的差不超过 $limit$。

可以使用我多次分享的滑动窗口模板解决，模板请见链接。

本题最大的难点在于快速地求滑动窗口内的最大值和最小值，类似题目如 480. 滑动窗口中位数。

如果遍历求滑动窗口内的最大值和最小值，时间复杂度是 $O(k)$，肯定会超时。降低时间复杂度的一个绝招就是增加空间复杂度：利用更好的数据结构。是的，我们的目的是快速让一组数据有序，那就寻找一个内部是有序的数据结构呗！下面我分语言讲解一下常见的内部有序的数据结构。

• 在 C++ 中 set/multiset/map 内部元素是有序的，它们都基于红黑树实现。其中 set 会对元素去重，而 multiset 可以有重复元素，map 是 key 有序的哈希表。
  - 在 Java 中 TreeSet 是有序的去重集合，TreeMap 是 key 有序的哈希表，它们也是基于红黑树实现的。
  - 在 Python 中 heapq 实现了堆算法，它不会对元素去重。

下面这个图是 C++ 的 multiset 内部结构示意图（Java 的 TreeSet 也是这样），它是个平衡二叉搜索树(BST)，插入元素时会自动调整二叉树，使得每个子树根节点的键值大于左子树所有节点的键值，同时保证根节点左右子树的高度相等。这样二叉树高度最小，检索速度最快。它的中序遍历是有序的，另外它也允许出现重复的值。

• 本题需要保存滑动窗口内的所有元素（可能含有重复元素），可以使用的 C++ 的 multiset/map 与 Java 中的 TreeMap。
  - 当频繁的插入和删除元素时，multiset/map 和 TreeMap 等有序的数据结构能够在在 $O(log(k))$ 的时间复杂度内调整 BST，从而维护结构的有序性。
  - multiset 和 TreeMap 都提供了获取第一个元素和最后一个元素的函数，也就能在 $O(1)$ 的时间内获取滑动窗口内最小值和最大值。

代码

有了非常高效的数据结构，做这个题已经不难了。我下面的代码演示了用 C++ 的 multiset 解决本题。代码不长，需要对 C++ 的 STL 有简单的了解。

• 使用 和 两个指针，分别指向滑动窗口的左右边界；定义 multiset 保存滑动窗口的所有元素；
• 主动右移： 指针每次移动一步，把 放入滑动窗口；
• 被动右移：判断此时窗口内最大值和最小值的差，如果大于 $limit$，则 指针被迫右移，直至窗口内最大值和最小值的差小于等于 $limit$ 为止；$left$ 每次右移之前，需要把 $A[left]$ 从 multiset 中减去一次。
• 滑动窗口长度的最大值就是所求。

  class Solution {
  public:
    int longestSubarray(vector<int>& nums, int limit) {
        multiset<int> st;
        int left = 0, right = 0;
        int res = 0;
        while (right < nums.size()) {
            st.insert(nums[right]);
            while (*st.rbegin() - *st.begin() > limit) {
                st.erase(st.find(nums[left]));
                left ++;
            }
            res = max(res, right - left + 1);
            right ++;
        }
        return res;
    }
  };

刷题心得

本题的重点在于快速求滑动窗口内的最大值和最小值。常见的方法有：

• 使用 multiset、TreeMap等数据结构；
  - 单调递增队列或者单调递减队列；

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

欢迎关注我的公众号：「每日算法题」。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！