# Title Description

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 = 4Output: 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 = 5Output: 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 = 0Output: 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 }```
58/60 passed test cases Overrun time 59th case is too long, initial thought optimization can not meet the requirements of the title.
The time overrun is mainly due to j's regression.
Because the maximum and minimum values of the interval change after i moves to the right, it needs to be searched again.

## 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.

## Monotonic Queue

Posted by khaldryck on Sun, 17 Apr 2022 01:55:19 +0930