从 O(NlogN) 到 O(N) 的优化：「二分滑动窗口」& 「双指针」 ...

宫水三叶的刷题日记

发布于 2021-02-26 15:57:56

8740

文章被收录于专栏：宫水三叶的刷题日记宫水三叶的刷题日记

题目描述

这是 LeetCode 上的「1438. 绝对差不超过限制的最长连续子数组」，难度为 Medium。

给你一个整数数组 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^5
1 <= nums[i] <= 10^9
0 <= limit <= 10^9

二分 + 滑动窗口解法

数据范围是

10^5

，因此只能考虑「对数解法」和「线性解法」。

对数解法很容易想到「二分」。

在给定 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})

，对于每次 check 而言，每个元素最多入队和出队常数次，复杂度为

O(n)

。整体复杂度为

O(n\log{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();
            }
            max.addLast(r);

            while (!min.isEmpty() && nums[r] <= nums[min.peekLast()]) {
                min.pollLast();
            }
            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)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.* 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。

「在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。」

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-02-22，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

腾讯云开发者社区

本文分享自宫水三叶的刷题日记微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

腾讯云开发者社区

登录后参与评论

0 条评论

热度