[LetCode-1438] 绝对差不超过限制的最长连续子数组

曾经终败给现在 2022-11-02 03:58 6阅读 0赞

### 题目 - letcode1438 ###

> 难度 - 中等  
> 给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
> 
> 如果不存在满足条件的子数组，则返回 0 。

*  示例 1

输入：nums = [8,2,4,7], limit = 4
    输出：2 
    解释：所有子数组如下：
    [8] 最大绝对差 |8-8| = 0 <= 4.
    [8,2] 最大绝对差 |8-2| = 6 > 4. 
    [8,2,4] 最大绝对差 |8-2| = 6 > 4.
    [8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
    [2] 最大绝对差 |2-2| = 0 <= 4.
    [2,4] 最大绝对差 |2-4| = 2 <= 4.
    [2,4,7] 最大绝对差 |2-7| = 5 > 4.
    [4] 最大绝对差 |4-4| = 0 <= 4.
    [4,7] 最大绝对差 |4-7| = 3 <= 4.
    [7] 最大绝对差 |7-7| = 0 <= 4. 
    因此，满足题意的最长子数组的长度为 2 。

*  示例 2

输入：nums = [10,1,2,4,7,2], limit = 5
    输出：4 
    解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5 。

*  示例 3：

输入：nums = [4,2,2,2,4,4,2,2], limit = 0
    输出：3

*  代码地址  
    [https://github.com/SeanYanxml/letcode-all][https_github.com_SeanYanxml_letcode-all]

--------------------

### 审题操作 ###

*  题目中, 要求的是获取`最大值`和`最小值`.
 *  题目要求输出的结果是数字的连续长度, 所以不要错误的把绝对值差值直接输出. `我就犯了这个错误`.

--------------------

### 思路1 ###

##### 顺序扫描 #####

*  先比较(0-1) (0-2) (0-3) 选择满足的条件.
 *  然后缩短头结点范围(1-2) (1-3)
 *  不断缩小. 直到数字个数为1.

不难写出如下代码:

class Solution {
        // 实际上是求最大值和最小值
        // 注意审题: 最大是求的长度
        public int longestSubarray(int[] nums, int limit) {
            int lastOkLimitLength = 0;
            for(int i=0; i<nums.length; i++){
                // 头结点 从i开始计算
                int max = nums[i], min = nums[i];
                for(int j=i;j<nums.length;j++){
                    // 最大值和最小值都从头开始计算
                    if(nums[j]>max){max = nums[j];}
                    else if(nums[j]<min){min=nums[j];}
                          // 比较
                    int limitNum = Math.abs(max-min);
                    int limitLength = j-i+1;
                    if(limitLength > lastOkLimitLength && limitNum <= limit ){
                    	    lastOkLimitLength = limitLength;
                    }   
                }
            }
            return lastOkLimitLength;
        }
    }
    # 这边错误的把绝对值当长度进行输出了. 这是一个错误的情况.

### 恐怖的测试用例 ###

*  case 1 - 大概2000多数字

[7386080,9043369,566116,155607,2192513,5102709,8009203,8124311,9220099,588704,7572203,4133378,3288454,1209376,224215,7213885,2408989,70926,953383,8985909,4537104,5409806,1128621,3708522,50534,9108260,2259019,1611400,5863523,3355077,4658980,8074627,2922137,7764681,2408538,8959208,5315886,2714416,6616752,...]
    6466408

*  case 2 - 相同数字1 - 大概4000多数字

[[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1...]
    10

### 局部优化 ###

*  1 绝对值大小判断优化  
    我们发现. `limit`和`最大-最小`相关. 只有当`最大`/`最小`变化的时候才会出现变化.
    
     *  当某一次变化时, 不满足`<limit`条件. 那么后续的数字也就无需判断了.
     *  当`最大/最小`变化时. 需要重新判断.
 *  2 外层循环结束条件  
    因为, 我们寻找的是最大的长度. 所以当`index=i时`，如果满足`length-i`的最大长度. 表示整个长度都符合. 那么后续的操作也就无需进行判断.
 *  3 注意数字相同的情况 - Case2

#具体优化操作算法
    # 注意点1 - 优化
    	outerJ: 
    			for (int j = i; j < nums.length; j++) {
    				// 优化点2 - 有数字变化再进行比较
    				flag = false;
    				// 最大值和最小值都从头开始计算
    				if (nums[j] > max) {
    					max = nums[j];
    					flag = true;
    				} else if (nums[j] < min) {
    					min = nums[j];
    					flag = true;
    				}
    
    				if (flag) {
    					// 优化点1
    					// 比较
    					int limitNum = Math.abs(max - min);
    					// int limitLength = j-i+1;
    					if (limitNum <= limit) {
    						// if(limitLength > lastOkLimitLength) {
    						// }
    						length++;
    					} else {
    						break outerJ;
    					}
    				} else {
    					length++;
    				}
    	}
    
    # 注意点 2 - 优化
    if(lastOkLimitLength >= ((nums.length-i+1)-1)) {
         break outerI;
    }

--------------------

### 思路2 ###

略. 感觉一定有什么比`O(N^N)`时间复杂度高的算法. 有时间再继续探索吧.

--------------------

### 结论 ###

可以看到. 这个题目不是特别的难. 获取判断最大最小值, 随后获取差值. 但是其中的2个测试用例想要不超时. 还是需要如上的3个优化操作的.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA0MTYxMDE_size_16_color_FFFFFF_t_70]  
提交记录惨不忍睹. 汗.

--------------------

### Reference ###

\[1\] [letcode-1438][]  
\[2\] [https://github.com/SeanYanxml/letcode-all][https_github.com_SeanYanxml_letcode-all]

[https_github.com_SeanYanxml_letcode-all]: https://github.com/SeanYanxml/letcode-all
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA0MTYxMDE_size_16_color_FFFFFF_t_70]: /images/20221024/4b59d8dece244639900e3ae1eed796c3.png
[letcode-1438]: https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/