LeetCode 每日一题

image.png

思路

对于数组区间求最值的话,还是可以借助滑动窗口/双指针算法进行处理,对于之前总结的模板,主要还是解决左指针、右指针移动的条件。

*右指针是否右移条件:当窗口区间元素绝对差值小于limit 那么就右移,否则不移动
*左指针是否右移条件:当右指针不移动的时候说明窗口区间已经出现满不足最大绝对值小于limit,那么找出满足最大绝对值小于limit的区间长度。

处理技巧:对于绝对值最大情况的区间判断,可以通过对子区间 sort 排序之后进行处理但是这样多了自处理的过程,其实这里可以借助 有序集合 TreeMap 进行处理。

代码

public class Solution{
    public int longestSubArray(int[] nums, int limit){
        TreeMap<Integer,Integer> map = new TreeMap<Integer,Integer>();
        int len = nums.length, left = 0, right = 0, res = 0;
        while(right<len){
            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[left] == 0){
                    map.remove(nums[left]);
                }
                left++;
            }
            res  = Math.max(res, right-left+1);
        }
        return res;
    }
}

关于作者

Kirago
扯淡第一名
获得点赞
文章被阅读