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

https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        TreeMap<Integer, Deque<Integer>> map = new TreeMap<>();
        int ans = 0;
        int i = 0;
        int j = 0;
        while (j < nums.length) {
            Deque<Integer> indexes = map.get(nums[j]);
            if (indexes == null) {
                indexes = new ArrayDeque<>();
            }
            if (indexes.isEmpty() || indexes.peekLast() != j) {
                indexes.offerLast(j);
                map.put(nums[j], indexes);
            }
            
            int max = map.lastKey();
            int min = map.firstKey();
            if (max - min > limit) {
                Deque<Integer> iIndexes = map.get(nums[i]);
                iIndexes.pollFirst();
                if (iIndexes.size() == 0) {
                    map.remove(nums[i]);
                } else {
                    map.put(nums[i], iIndexes);
                }
                i++;
            } else {
                ans = Math.max(ans, j - i + 1);
                j++;
            }
        }
        return ans;
    }
}

sliding window + treemap + deque,之所以可以用sliding window是因为它要求区间里任意两对数的diff不超过limit,因此只要区间不满足条件左指针就可以往前移动,然后就是用treemap来维护区间里面的最大值和最小值以及对应坐标们,坐标似乎也不用deque来存?

Last updated