Title Description

1438. Maximum continuous subarray with absolute difference not exceeding limit Medium difficulty

Give you an array of integers nums and an integer limit that represents a limit. Return the length of the longest continuous subarray in which the absolute difference between any two elements must be less than or equal to a limit.

Returns 0 if there is no subarray that meets the criteria.

Example 1:

Input: nums = [8,2,4,7], limit = 4
Output: 2 
Interpretation: All subarrays are as follows:
[8]Maximum absolute difference|8-8| = 0 <= 4.
[8,2] Maximum Absolute Difference | 8-2 | = 6 > 4. 
[8,2,4]Maximum absolute difference|8-2| = 6 > 4.
[8,2,4,7]Maximum absolute difference|8-2| = 6 > 4.
[2] Maximum absolute difference |2-2| = 0 <= 4.
[2,4] Maximum Absolute Difference |2-4| = 2 <= 4.
[2,4,7] Maximum Absolute Difference |2-7| = 5 > 4.
[4] Maximum absolute difference |4-4| = 0 <= 4.
[4,7] Maximum Absolute Difference |4-7| = 3 <= 4.
[7] Maximum absolute difference |7-7| = 0 <= 4. 
Therefore, the longest subarray that satisfies the title is 2.

Example 2:

Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4 
Explanation: The longest child array that satisfies the title is [2,4,7,2], and its maximum absolute difference |2-7| = 5 <= 5.

Example 3:

Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3

Problem

The absolute difference between any two elements must be less than or equal to the limit, which can be converted to the absolute value of the maximum and minimum in the selected interval being less than or equal to the limit. Therefore, the title is converted to an absolute value that is less than or equal to the length of the maximum continuous subarray of the limit.

Sliding windows are easy to think of for continuous subarray problems.

Initial ideas

Code:

 1 class Solution {
 2     public int longestSubarray(int[] nums, int limit) {
 3         int minNum = Integer.MAX_VALUE;
 4         int minIndex = -1;
 5         int maxNum = Integer.MIN_VALUE;
 6         int longest = 0;
 7         int maxIndex = -1;
 8         int i,j;
 9         for(i=0,j=0;j < nums.length;){
10             if(nums[j]<minNum){
11                 minNum = nums[j];
12                 minIndex = j;
13             }
14             if(nums[j]>maxNum){
15                 maxNum = nums[j];
16                 maxIndex = j;
17             }
18             if(Math.abs(maxNum - minNum) <= limit){//Satisfies the criteria and slides j to the right of the window
19                 j++;
20             }else{
21                 longest = Math.max(longest,j - i);
22                 i = Math.min(minIndex,maxIndex) + 1;//Not satisfied, left side of window i right slide
23                 j = i;
24                 maxNum = Integer.MIN_VALUE;
25                 minNum = Integer.MAX_VALUE;
26             }
27         }
28         longest = Math.max(longest,j - i);
29         return longest;
30     }
31 }

Attempts to improve (to be added later)

Code:

 1 class Solution {
 2     public int longestSubarray(int[] nums, int limit) {
 3         int minNum = Integer.MAX_VALUE;
 4         int minIndex = -1;
 5         int maxNum = Integer.MIN_VALUE;
 6         int maxIndex = -1;
 7         int sminNum = Integer.MAX_VALUE;
 8         int sminIndex = -1;
 9         int smaxNum = Integer.MIN_VALUE;
10         int smaxIndex = -1;
11         int longest = 0;
12         int i,j;
13         for(i=0,j=0;j < nums.length&&i <= j;){
14             if(nums[j]<minNum){
15                 if(minNum<sminNum){
16                     sminNum = minNum;
17                     sminIndex = minIndex;
18                 }
19                 minNum = nums[j];
20                 minIndex = j;
21             }else if(nums[j]<sminNum){
22                 sminNum = nums[j];
23                 sminIndex = j;
24             }
25             if(nums[j]>maxNum){
26                 if(maxNum>smaxNum){
27                     smaxNum = maxNum;
28                     smaxIndex = maxIndex;
29                 }
30                 maxNum = nums[j];
31                 maxIndex = j;
32             }else if(nums[j]>smaxNum){
33                 smaxNum = nums[j];
34                 smaxIndex = j;
35             }
36             if(Math.abs(maxNum - minNum) <= limit){
37                 j++;
38             }else{
39                 longest = Math.max(longest,j - i);
40                 i = Math.min(minIndex,maxIndex);
41                 if(i == minIndex){
42                     minNum = sminNum;
43                     minIndex = sminIndex;
44                     sminNum = Integer.MAX_VALUE;
45                     sminIndex = -1;
46                 }else{
47                     maxNum = smaxNum;
48                     maxIndex = smaxIndex;
49                     smaxNum = Integer.MIN_VALUE;
50                     smaxIndex = -1;
51                 }
52                 i += 1;
53             }
54         }
55         longest = Math.max(longest,j - i);
56         return longest;
57     }
58 }

i want to record the largest, second largest, smallest, second smallest values and their positions so that when i slides right, j does not fall back and the second largest becomes the maximum (or the second smallest becomes the minimum). But it did not succeed in the end.

Red-Black Tree Solution

Monotonic Queue