LeetCode 1438

Link: leetcode.com/problems/lo…

Method 1: TreeMap

For example, if the longest subarray with XXXXXX is the longest, it looks like a window. For example, if the longest subarray is the longest, it looks like a window. Then the problem is nothing more than how to dynamically solve the maximum and minimum value of the entire window when sliding the window. The easy one to think of is TreeMap, because TreeMap’s keys are ordered and you can take first and last keys directly. So I’m done with the sliding window, for I on the outside, while J on the inside. Code:

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        int i = 0, j = 0, n = nums.length;
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int res = 0;
        
        for (; i < n; i++) {
            while (j < n && (map.isEmpty() || (!map.isEmpty() && Math.abs(nums[j] - map.firstKey()) <= limit && Math.abs(nums[j] - map.lastKey()) <= limit))) {
                int tmp = map.getOrDefault(nums[j], 0) + 1;
                map.put(nums[j], tmp);
                j++;
            }
            
            res = Math.max(res, j - i);
            
            int tmp = map.get(nums[i]) - 1;
            if (tmp == 0) map.remove(nums[i]);
            else {
                map.put(nums[i], tmp);
            }
        }
        
        return res;
    }
}
Copy the code

Method 2: Monotonic queue

: time complexity O (n) reference: learning from the flower sauce zxi.mytechroad.com/blog/queue/… Idea: This is what makes this problem worth learning. For maximizing and minimizing Windows, we use monotone queues. In fact, in Java we use a double-endian queue Deque. For example, the queue that we use to dynamically maximize, we call maxQ. So maxQ, every time we put an element in, we’re going to put it from last, and we’re going to maintain this queue from first to last and it’s going to be monotonically constant (difference <=0), so if that’s the case, every time we take an element from first, we’re going to get the maximum number of elements in here. So why can we use monotone without increasing, instead of monotone decreasing? If (maxq.getFirst () == nums[l]) maxq.pollFirst (); , because if there are several with equal to the value of the maximum heap at the first the end of the queue, say, k such elements, so anyway I know the window inside a total of k value, the nums [l] delete it doesn’t matter, anyway, deleted from the queue after take out the maximum or the value, because of which has a window. It’s a little more convenient to write it this way. Code:

class Solution { public int longestSubarray(int[] nums, int limit) { int res = 0, l = 0; Deque<Integer> maxQ = new ArrayDeque<>(); Deque<Integer> minQ = new ArrayDeque<>(); for (int r = 0; r < nums.length; r++) { while (! maxQ.isEmpty() && maxQ.getLast() < nums[r]) { maxQ.pollLast(); } while (! minQ.isEmpty() && minQ.getLast() > nums[r]) { minQ.pollLast(); } minQ.addLast(nums[r]); maxQ.addLast(nums[r]); while (maxQ.getFirst() - minQ.getFirst() > limit) { if (maxQ.getFirst() == nums[l]) maxQ.pollFirst(); if (minQ.getFirst() == nums[l]) minQ.pollFirst(); l++; } res = Math.max(res, r - l + 1); } return res; }}Copy the code