题目描述
这是 LeetCode 上的 1438. 绝对差不超过限制的最长连续子数组 ，难度为 中等。
Tag : 「滑动窗口」、「单调队列」、「二分」
给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
如果不存在满足条件的子数组，则返回 0 。
示例 1：
输入：nums = [8,2,4,7], limit = 4 输出：2 解释：所有子数组如下： [8] 最大绝对差 |8-8| = 0 <= 4. [8,2] 最大绝对差 |8-2| = 6 > 4. [8,2,4] 最大绝对差 |8-2| = 6 > 4. [8,2,4,7] 最大绝对差 |8-2| = 6 > 4. [2] 最大绝对差 |2-2| = 0 <= 4. [2,4] 最大绝对差 |2-4| = 2 <= 4. [2,4,7] 最大绝对差 |2-7| = 5 > 4. [4] 最大绝对差 |4-4| = 0 <= 4. [4,7] 最大绝对差 |4-7| = 3 <= 4. [7] 最大绝对差 |7-7| = 0 <= 4. 因此，满足题意的最长子数组的长度为 2 。 复制代码
示例 2：
输入：nums = [10,1,2,4,7,2], limit = 5 输出：4 解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5 。 复制代码
示例 3：
输入：nums = [4,2,2,2,4,4,2,2], limit = 0 输出：3 复制代码
提示：
- 1 <= nums.length <= 10^5105
- 1 <= nums[i] <= 10^9109
- 0 <= limit <= 10^9109
二分 + 滑动窗口
数据范围是 10^5105，因此只能考虑「对数解法」和「线性解法」。
对数解法很容易想到「二分」。
在给定 limit 的情况下，倘若有「恰好」满足条件的区间长度为 len，必然存在满足条件且长度小于等于 len 的区间，同时必然不存在长度大于 len 且满足条件的区间。
因此长度 len 在数轴中具有「二段性」。
问题转化为「如何判断 nums 中是否有长度 len 的区间满足绝对值不超过 limit」
我们可以枚举区间的右端点 r，那么对应的左端点为 r - len + 1，然后使用「单调队列」来保存区间的最大值和最小值。
class Solution { public int longestSubarray(int[] nums, int limit) { int n = nums.length; int l = 1, r = n; while (l < r) { int mid = l + r + 1 >> 1; if (check(nums, mid, limit)) { l = mid; } else { r = mid - 1; } } return r; } boolean check(int[] nums, int len, int limit) { int n = nums.length; Deque<Integer> max = new ArrayDeque<>(), min = new ArrayDeque<>(); for (int r = 0, l = r - len + 1; r < n; r++, l = r - len + 1) { if (!max.isEmpty() && max.peekFirst() < l) max.pollFirst(); while (!max.isEmpty() && nums[r] >= nums[max.peekLast()]) max.pollLast(); max.addLast(r); if (!min.isEmpty() && min.peekFirst() < l) min.pollFirst(); while (!min.isEmpty() && nums[r] <= nums[min.peekLast()]) min.pollLast(); min.addLast(r); if (l >= 0 && Math.abs(nums[max.peekFirst()] - nums[min.peekFirst()]) <= limit) return true; } return false; } } 复制代码
- 时间复杂度：枚举长度的复杂度为 O(\log{n})O(logn)，对于每次
check而言，每个元素最多入队和出队常数次，复杂度为 O(n)O(n)。整体复杂度为 O(n\log{n})O(nlogn) - 空间复杂度：O(n)O(n)
双指针
上述解法我们是在对 len 进行二分，而事实上我们可以直接使用「双指针」解法找到最大值。
始终让右端点 r 右移，当不满足条件时让 l 进行右移。
同时，还是使用「单调队列」保存我们的区间最值，这样我们只需要对数组进行一次扫描即可得到答案。
class Solution { public int longestSubarray(int[] nums, int limit) { int n = nums.length; int ans = 0; Deque<Integer> max = new ArrayDeque<>(), min = new ArrayDeque<>(); for (int r = 0, l = 0; r < n; r++) { while (!max.isEmpty() && nums[r] >= nums[max.peekLast()]) max.pollLast(); while (!min.isEmpty() && nums[r] <= nums[min.peekLast()]) min.pollLast(); max.addLast(r); min.addLast(r); while (Math.abs(nums[max.peekFirst()] - nums[min.peekFirst()]) > limit) { l++; if (max.peekFirst() < l) max.pollFirst(); if (min.peekFirst() < l) min.pollFirst(); } ans = Math.max(ans, r - l + 1); } return ans; } } 复制代码
- 时间复杂度：每个元素最多入队和出队常数次，复杂度为 O(n)O(n)
- 空间复杂度：O(n)O(n)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1438 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
