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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:23 2023-09-13 16:06:23 Updated    

给你一个整数数组 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

方法一：滑动窗口 + 有序集合

思路和解法

我们可以枚举每一个位置作为右端点，找到其对应的最靠左的左端点，满足区间中最大值与最小值的差不超过 limit。

注意到随着右端点向右移动，左端点也将向右移动，于是我们可以使用滑动窗口解决本题。

为了方便统计当前窗口内的最大值与最小值，我们可以使用平衡树：

  • 语言自带的红黑树，例如 C++ 中的 std::multiset，Java 中的 TreeMap；

  • 第三方的平衡树库，例如 Python 中的 sortedcontainers（事实上，这个库的底层实现并不是平衡树，但各种操作的时间复杂度仍然很优秀）；

  • 手写 Treap 一类的平衡树，例如下面的 Golang 代码。

来维护窗口内元素构成的有序集合。

代码

对于 Python 语言，力扣平台支持 sortedcontainers，但其没有默认被导入（import）。读者可以参考 Python Sorted Containers 了解该第三方库的使用方法。

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        multiset<int> s;
        int n = nums.size();
        int left = 0, right = 0;
        int ret = 0;
        while (right < n) {
            s.insert(nums[right]);
            while (*s.rbegin() - *s.begin() > limit) {
                s.erase(s.find(nums[left++]));
            }
            ret = max(ret, right - left + 1);
            right++;
        }
        return ret;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int longestSubarray(int[] nums, int limit) {
        TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
        int n = nums.length;
        int left = 0, right = 0;
        int ret = 0;
        while (right < n) {
            map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
            while (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++;
            }
            ret = Math.max(ret, right - left + 1);
            right++;
        }
        return ret;
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        s = SortedList()
        n = len(nums)
        left = right = ret = 0

        while right < n:
            s.add(nums[right])
            while s[-1] - s[0] > limit:
                s.remove(nums[left])
                left += 1
            ret = max(ret, right - left + 1)
            right += 1
        
        return ret
[sol1-Golang]
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
import "math/rand"

type node struct {
    ch       [2]*node
    priority int
    key      int
    cnt      int
}

func (o *node) cmp(b int) int {
    switch {
    case b < o.key:
        return 0
    case b > o.key:
        return 1
    default:
        return -1
    }
}

func (o *node) rotate(d int) *node {
    x := o.ch[d^1]
    o.ch[d^1] = x.ch[d]
    x.ch[d] = o
    return x
}

type treap struct {
    root *node
}

func (t *treap) ins(o *node, key int) *node {
    if o == nil {
        return &node{priority: rand.Int(), key: key, cnt: 1}
    }
    if d := o.cmp(key); d >= 0 {
        o.ch[d] = t.ins(o.ch[d], key)
        if o.ch[d].priority > o.priority {
            o = o.rotate(d ^ 1)
        }
    } else {
        o.cnt++
    }
    return o
}

func (t *treap) del(o *node, key int) *node {
    if o == nil {
        return nil
    }
    if d := o.cmp(key); d >= 0 {
        o.ch[d] = t.del(o.ch[d], key)
    } else {
        if o.cnt > 1 {
            o.cnt--
        } else {
            if o.ch[1] == nil {
                return o.ch[0]
            }
            if o.ch[0] == nil {
                return o.ch[1]
            }
            d = 0
            if o.ch[0].priority > o.ch[1].priority {
                d = 1
            }
            o = o.rotate(d)
            o.ch[d] = t.del(o.ch[d], key)
        }
    }
    return o
}

func (t *treap) insert(key int) {
    t.root = t.ins(t.root, key)
}

func (t *treap) delete(key int) {
    t.root = t.del(t.root, key)
}

func (t *treap) min() (min *node) {
    for o := t.root; o != nil; o = o.ch[0] {
        min = o
    }
    return
}

func (t *treap) max() (max *node) {
    for o := t.root; o != nil; o = o.ch[1] {
        max = o
    }
    return
}

func longestSubarray(nums []int, limit int) (ans int) {
    t := &treap{}
    left := 0
    for right, v := range nums {
        t.insert(v)
        for t.max().key-t.min().key > limit {
            t.delete(nums[left])
            left++
        }
        ans = max(ans, right-left+1)
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

  • 时间复杂度：O(n \log n)，其中 n 是数组长度。向有序集合中添加或删除元素都是 O(\log n) 的时间复杂度。每个元素最多被添加与删除一次。

  • 空间复杂度：O(n)，其中 n 是数组长度。最坏情况下有序集合将和原数组等大。

方法二：滑动窗口 + 单调队列

思路和解法

在方法一中，我们仅需要统计当前窗口内的最大值与最小值，因此我们也可以分别使用两个单调队列解决本题。

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

代码

[sol2-C++]
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(vector<int>& nums, int limit) {
        deque<int> queMax, queMin;
        int n = nums.size();
        int left = 0, right = 0;
        int ret = 0;
        while (right < n) {
            while (!queMax.empty() && queMax.back() < nums[right]) {
                queMax.pop_back();
            }
            while (!queMin.empty() && queMin.back() > nums[right]) {
                queMin.pop_back();
            }
            queMax.push_back(nums[right]);
            queMin.push_back(nums[right]);
            while (!queMax.empty() && !queMin.empty() && queMax.front() - queMin.front() > limit) {
                if (nums[left] == queMin.front()) {
                    queMin.pop_front();
                }
                if (nums[left] == queMax.front()) {
                    queMax.pop_front();
                }
                left++;
            }
            ret = max(ret, right - left + 1);
            right++;
        }
        return ret;
    }
};
[sol2-Java]
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;
    }
}
[sol2-JavaScript]
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
var longestSubarray = function(nums, limit) {
    const queMax = [];
    const queMin = [];
    const n = nums.length;
    let left = 0, right = 0;
    let ret = 0;
    while (right < n) {
        while (queMax.length && queMax[queMax.length - 1] < nums[right]) {
            queMax.pop();
        }
        while (queMin.length && queMin[queMin.length - 1] > nums[right]) {
            queMin.pop();
        }
        queMax.push(nums[right]);
        queMin.push(nums[right]);
        while (queMax.length && queMin.length && queMax[0] - queMin[0] > limit) {
            if (nums[left] === queMin[0]) {
                queMin.shift();
            }
            if (nums[left] === queMax[0]) {
                queMax.shift();
            }
            left++;
        }
        ret = Math.max(ret, right - left + 1);
        right++;
    }
    return ret;
};
[sol2-Python3]
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
class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        n = len(nums)
        queMax, queMin = deque(), deque()
        left = right = ret = 0

        while right < n:
            while queMax and queMax[-1] < nums[right]:
                queMax.pop()
            while queMin and queMin[-1] > nums[right]:
                queMin.pop()
            
            queMax.append(nums[right])
            queMin.append(nums[right])

            while queMax and queMin and queMax[0] - queMin[0] > limit:
                if nums[left] == queMin[0]:
                    queMin.popleft()
                if nums[left] == queMax[0]:
                    queMax.popleft()
                left += 1
            
            ret = max(ret, right - left + 1)
            right += 1
        
        return ret
[sol2-Golang]
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
func longestSubarray(nums []int, limit int) (ans int) {
    var minQ, maxQ []int
    left := 0
    for right, v := range nums {
        for len(minQ) > 0 && minQ[len(minQ)-1] > v {
            minQ = minQ[:len(minQ)-1]
        }
        minQ = append(minQ, v)
        for len(maxQ) > 0 && maxQ[len(maxQ)-1] < v {
            maxQ = maxQ[:len(maxQ)-1]
        }
        maxQ = append(maxQ, v)
        for len(minQ) > 0 && len(maxQ) > 0 && maxQ[0]-minQ[0] > limit {
            if nums[left] == minQ[0] {
                minQ = minQ[1:]
            }
            if nums[left] == maxQ[0] {
                maxQ = maxQ[1:]
            }
            left++
        }
        ans = max(ans, right-left+1)
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
[sol2-C]
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
int longestSubarray(int* nums, int numsSize, int limit) {
    int queMax[numsSize], queMin[numsSize];
    int leftMax = 0, rightMax = 0;
    int leftMin = 0, rightMin = 0;
    int left = 0, right = 0;
    int ret = 0;
    while (right < numsSize) {
        while (leftMax < rightMax && queMax[rightMax - 1] < nums[right]) {
            rightMax--;
        }
        while (leftMin < rightMin && queMin[rightMin - 1] > nums[right]) {
            rightMin--;
        }
        queMax[rightMax++] = nums[right];
        queMin[rightMin++] = nums[right];
        while (leftMax < rightMax && leftMin < rightMin && queMax[leftMax] - queMin[leftMin] > limit) {
            if (nums[left] == queMin[leftMin]) {
                leftMin++;
            }
            if (nums[left] == queMax[leftMax]) {
                leftMax++;
            }
            left++;
        }
        ret = fmax(ret, right - left + 1);
        right++;
    }
    return ret;
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组长度。我们最多遍历该数组两次，两个单调队列入队出队次数也均为 O(n)。

  • 空间复杂度：O(n)，其中 n 是数组长度。最坏情况下单调队列将和原数组等大。

 Comments
On this page
1438-绝对差不超过限制的最长连续子数组