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

发表于
本文字数： 4.3k 阅读时长 ≈ 4 分钟

LeetCode每日一题，1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

先看题目描述

yoe158.png

大意就是给定一个数组 nums 和一个整数 limit，让我们求出 nums 的最长连续子数组长度，该子数组满足其中最大值和最小值之差不超过 limit

算法和思路

滑动窗口

这题很快就想到用滑动窗口做，当滑动窗口内的最大值与最小值之差不超过 limit 时扩张滑动窗口，否则就移动滑动窗口，最后返回滑动窗口的长度即可。这题的难点在于如何快速的求出滑动窗口内的最大值与最小值，如果通过遍历滑动窗口内元素来求，时间复杂度过高，我们可以通过采用合适的数据结构，来优化时间复杂度。下面的代码中将展示三种数据结构的写法

算法源码

滑动窗口+优先级队列

可以使用两个优先级队列，分别按照升序和降序存储滑动窗口内元素，从而得到滑动窗口内元素的最大值和最小值，代码中使用到了延迟删除的技巧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public int longestSubarray(int[] nums, int limit) {
        int len = nums.length;
        int left = 0;
        int right = 0;
        PriorityQueue<Integer> small = new PriorityQueue<>((a, b) -> a - b);
        PriorityQueue<Integer> large = new PriorityQueue<>((a, b) -> b - a);
        Map<Integer, Integer> delayed1 = new HashMap<>();
        Map<Integer, Integer> delayed2 = new HashMap<>();
        while (right < len) {
            int num = nums[right];
            small.offer(num);
            large.offer(num);
            right++;
            if ((large.peek() - small.peek()) > limit) {
                int delete = nums[left];
                delayed1.put(delete, delayed1.getOrDefault(delete, 0) + 1);
                delayed2.put(delete, delayed2.getOrDefault(delete, 0) + 1);
                while (delayed1.containsKey(small.peek())) {
                    int cnt = delayed1.get(small.peek());
                    if (cnt == 1) {
                        delayed1.remove(small.peek());
                    } else {
                        delayed1.put(small.peek(), cnt - 1);
                    }
                    small.poll();
                }
                while (delayed2.containsKey(large.peek())) {
                    int cnt = delayed2.get(large.peek());
                    if (cnt == 1) {
                        delayed2.remove(large.peek());
                    } else {
                        delayed2.put(large.peek(), cnt - 1);
                    }
                    large.poll();
                }
                left++;
            }
        }
        return right - left;
    }
}

滑动窗口+有序集合

为了方便统计滑动窗口内的最大值与最小值，我们可以使用平衡树来维护窗口内元素的有序集合，例如 Java 语言中自带的红黑树 TreeMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int longestSubarray(int[] nums, int limit) {
        int len = nums.length;
        int left = 0;
        int right = 0;
        TreeMap<Integer, Integer> map = new TreeMap<>();
        while (right < len) {
            map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
            right++;
            if ((map.lastKey() - map.firstKey()) > limit) {
                map.put(nums[left], map.get(nums[left]) - 1);
                if (map.get(nums[left]) == 0) {
                    map.remove(nums[left]);
                }
                left++;
            }
        }
        return right - left;
    }
}

滑动窗口+单调队列

在实际代码中，我们使用一个单调递增的队列 queMin 维护最小值，一个单调递减的队列 queMax 维护最大值。这样我们只需要计算两个队列的队首的差值，即可知道当前窗口是否满足条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int longestSubarray(int[] nums, int limit) {
        Deque<Integer> queMax = new LinkedList<Integer>();
        Deque<Integer> queMin = new LinkedList<Integer>();
        int n = nums.length;
        int left = 0, right = 0;
        int ret = 0;
        while (right < n) {
            while (!queMax.isEmpty() && queMax.peekLast() < nums[right]) {
                queMax.pollLast();
            }
            while (!queMin.isEmpty() && queMin.peekLast() > nums[right]) {
                queMin.pollLast();
            }
            queMax.offerLast(nums[right]);
            queMin.offerLast(nums[right]);
            while (!queMax.isEmpty() && !queMin.isEmpty() && queMax.peekFirst() - queMin.peekFirst() > limit) {
                if (nums[left] == queMin.peekFirst()) {
                    queMin.pollFirst();
                }
                if (nums[left] == queMax.peekFirst()) {
                    queMax.pollFirst();
                }
                left++;
            }
            ret = Math.max(ret, right - left + 1);
            right++;
        }
        return ret;
    }
}