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

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

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

# 思路

    Deque<Integer> dq1 = new ArrayDeque();
    Deque<Integer> dq2 = new ArrayDeque();

# 解法


class Solution {
    public int longestSubarray(int[] nums, int limit) {
        Deque<Integer> dq1 = new ArrayDeque();
        Deque<Integer> dq2 = new ArrayDeque();

        int n = nums.length;
        int ans = 0;

        int minIndex = 0;
        int maxIndex = 0;
        int beginIndex = 0;
        for(int i = 0; i < n; i++){
            while(!dq1.isEmpty() && nums[i] > nums[dq1.getLast()]){
                dq1.pollLast();
            }
            dq1.addLast(i);
            while(!dq2.isEmpty() && nums[i] < nums[dq2.getLast()]){
                dq2.pollLast();
            }
            dq2.addLast(i);

            maxIndex = dq1.peek();
            minIndex = dq2.peek();


            int diff = nums[maxIndex] - nums[minIndex];

            if(diff <= limit){
                ans = Math.max(i-beginIndex+1,ans);
            }else{
                if(minIndex < maxIndex){
                    while(!dq2.isEmpty() && nums[maxIndex] - nums[dq2.peek()] > limit){
                       beginIndex =  dq2.pollFirst() + 1;
                    }
                    if(dq2.isEmpty()){
                        dq2.addLast(i);
                    }
                    
                }else{
                    while(!dq1.isEmpty() && nums[dq1.peek()] - nums[minIndex] > limit){
                        beginIndex =  dq1.pollFirst() + 1;
                    }
                    if(dq1.isEmpty()){
                        dq1.addLast(i);
                    }
                   
                }
            }
        }
        return ans;
    }
}

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

# 总结

分析出几种情况，然后分别对各个情况实现

#Java