您的位置 首页 java

「LeetCode」差不超过限制的最长连续子数组Java题解

题目

给你一个整数数组 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按照自然序排序。

* 每天坚持一题,加油!

文章来源:智云一二三科技

文章标题:「LeetCode」差不超过限制的最长连续子数组Java题解

文章地址:https://www.zhihuclub.com/190506.shtml

关于作者: 智云科技

热门文章

发表回复

您的电子邮箱地址不会被公开。

网站地图