1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

,

TreeMap + Sliding Window

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int longestSubarray(int[] nums, int limit) {
        int maxLength = 1;

        TreeMap<Integer, Integer> windowCountMap = new TreeMap<>();

        int i = 0; // window: [i, j]
        for (int j = 0; j < nums.length; j++) {
            windowCountMap.put(nums[j], windowCountMap.getOrDefault(nums[j], 0) + 1);
            while (windowCountMap.lastKey() - windowCountMap.firstKey() > limit) {
                // 收缩窗口
                windowCountMap.put(nums[i], windowCountMap.get(nums[i]) - 1);
                if (windowCountMap.get(nums[i]) == 0) {
                    windowCountMap.remove(nums[i]);
                }
                i++;
            }

            maxLength = Math.max(maxLength, j - i + 1);
        }

        return maxLength;
    }
}

Monotonic Queue + Sliding Window

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
class Solution {
    public int longestSubarray(int[] nums, int limit) {
        Deque<Integer> increaseDeque = new LinkedList<>(); // 非严格单调递增队列
        Deque<Integer> decreaseDeque = new LinkedList<>(); // 非严格单调递减队列

        int maxLength = 1;

        int i = 0; // window: [i, j]
        for (int j = 0; j < nums.length; j++) {
            while (!increaseDeque.isEmpty() && nums[j] > increaseDeque.getFirst()) {
                increaseDeque.pollFirst();
            }
            increaseDeque.offerFirst(nums[j]);
            while (!decreaseDeque.isEmpty() && nums[j] < decreaseDeque.getFirst()) {
                decreaseDeque.pollFirst();
            }
            decreaseDeque.offerFirst(nums[j]);

            int maxValue = increaseDeque.getLast(), minValue = decreaseDeque.getLast();
            while (maxValue - minValue > limit) {
                // 收缩窗口

                if (nums[i] == maxValue) {
                    increaseDeque.pollLast();
                }
                if (nums[i] == minValue) {
                    decreaseDeque.pollLast();
                }
                i++;

                maxValue = increaseDeque.getLast();
                minValue = decreaseDeque.getLast();
            }

            maxLength = Math.max(maxLength, j - i + 1);
        }

        return maxLength;
    }
}

References

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit