原题链接:
https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/description/

解法1: 滑动窗口 + 单调队列

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 {
    /*
    *  滑动窗口
    *  使用left和right两个指针 分别指向滑动窗口的左右边界 使用TreeMap保存滑动窗口的所有元素
    *  right 主动右移 right每移动一步  把A[right] 放入滑动窗口
    *  left 被动右移 判断此时窗口内最大值和最小值的差 如果大于limit 则left指针被迫右移 left右移之前需要把A[left]从TreeMap中减去一次
    * */
    public int longestSubarray(int[] nums, int limit) {
        // 维护的就是滑动窗口 其排序规则 就是窗口的最大最小值
        // 数 以及 出现的次数
        TreeMap<Integer,Integer> mq = new TreeMap<>(((o1, o2) -> o1 - o2));
        int left = 0 , right = 0;
        int ans = 0;
        int n = nums.length;
        while (right < n){
            // right 主动右移
            // 出现一次 则记为1
            mq.put(nums[right], mq.getOrDefault(nums[right],0) + 1);
            // 如果最大值 - 减小值 > limit 即意味着 left应该左移
            while (mq.lastKey() - mq.firstKey() > limit){
                mq.put(nums[left],mq.get(nums[left]) - 1);
                // 如当前 nums[left] 已经不存在 则移除键值
                if(mq.get(nums[left]) == 0){
                    mq.remove(nums[left]);
                }
                left++;
             }

            // 先更新答案
            ans = Math.max(ans, right - left + 1);
            
            // right 每次都主动右移
            right++;
        }

        return ans;
    }
}