题目

给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。

如果不存在满足条件的子数组，则返回 0 。

代码

 public class DayCode {
    public static void main(String[] args) {
        int[] nums = new int[]{1,2,2,3,1,4,2};
        int limit = 2;
        int ans = new DayCode().longestSubarray(nums, limit);
        System.out.println("ans is " + ans);
    }
    /**
     * 
     * 时间复杂度 O(n log n)
     * 空间复杂度 O(n)
     * @param nums
     * @param limit
     * @return
     */    public int longestSubarray(int[] nums, int limit) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int n = nums.length;
        int left = 0;
        int right = 0;
        int ans = 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++;
            }
            ans = Math.max(ans, right - left + 1);
            right++;
        }
        return ans;
    }
}  

总结

* 这个题目是滑动窗口问题，主要是使用了 Java 实现好的TreeMap数据结构。

* TreeMap是Red-Black tree的实现，可以根据key按照自然序排序。

* 每天坚持一题，加油！