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

63 阅读 0 评论 42 点赞

我是靠谱客的博主缓慢早晨，最近开发中收集的这篇文章主要介绍[leetcode]1438. 绝对差不超过限制的最长连续子数组，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

个人博客：https://javaniuniu.com/
难度：中等
本题涉及算法： 滑动窗口
思路：滑动窗口
类似题型：
- 3. 无重复字符的最长子串
- 5393. 可获得的最大点数

题目 1438. 绝对差不超过限制的最长连续子数组

给你一个整数数组 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

提示：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= limit <= 10^9

方法一滑动窗口

解题思路

维护一直最大值和最小值
维护一个最长数组
$sub_nums增加的条件=begin{cases} abs(num - curr_max) <= limit & 判断当前元素是否复合条件，当前元素和数组中最大元素比较\ abs(num - curr_min) <= limit & 判断当前元素是否复合条件，当前元素和数组中最小元素比较 \ abs(curr_max - curr_min) <= limit & 判断数组中元素是否符合条件，数组中最大元素和最小元素比较 end{cases}$
当不复合数组增加条件，则以当前长度向后移动
在向后移动的同时，数组中元素也在在发生变化，所以需要更新数组中的最大最小值

执行过程举例 nums = [10,1,2,4,7,2] limit = 5

在这里插入图片描述

python

class Solution(object):
    def longestSubarray(self, nums, limit):
        if not nums:
            return 0
        curr_max = nums[0] # 当子数组下最大值 这里初始化为第一个数
        curr_min = nums[0] # 当子数组下最大值 这里初始化为第一个数
        sub_nums = [] # 以数组作为窗口滑动
        for num in nums:
            if abs(num - curr_max) <=  limit and abs(num - curr_min) <=  limit and abs(curr_max - curr_min) <= limit:
                curr_max = max(num,curr_max)
                curr_min = min(num,curr_min)
                sub_nums.append(num)
            else:    
                sub_nums.append(num)
                sub_nums.pop(0)
                curr_max = max(sub_nums) # 当子数组最大值
                curr_min = min(sub_nums) # 当前子数组最小值
        return  len(sub_nums)

java

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        if (nums ==null || nums.length==0)
            return 0;
        int curr_max = nums[0]; // 当子数组下最大值 这里初始化为第一个数
        int curr_min = nums[0]; // 当子数组下最大值 这里初始化为第一个数
        Queue<Integer> sub_nums = new LinkedList<>();
        for(int num:nums){
            if (Math.abs(num - curr_max) <=  limit && Math.abs(num - curr_min) <=  limit && Math.abs(curr_max - curr_min) <= limit) {
                curr_max = Math.max(num,curr_max);
                curr_min = Math.min(num,curr_min);
                sub_nums.offer(num);
            }else{
                sub_nums.offer(num);
                sub_nums.poll();
                curr_max = Collections.max(sub_nums); // 当子数组最大值
                curr_min = Collections.min(sub_nums); // 当前子数组最小值
            }
        }

        return sub_nums.size();
    }
}

错误代码

本想设计一个时间复杂度为 n 的结果错了尴尬

错误答案错在 [10,1,2,4,7,2] 5

class Solution(object):
    def longestSubarray(self, nums, limit):
        """
        :type nums: List[int]
        :type limit: int
        :rtype: int
        """
        if not nums:
            return 0
        curr_max = nums[0] # 当子数组下最大值 这里初始化为第一个数
        curr_min = nums[0] # 当子数组下最大值 这里初始化为第一个数
        len_max = 0 # 最长子数组长度
        len_curr = 0 # 当前子数组长度
        for num in nums:
            if abs(num - curr_max) <  limit and abs(num - curr_min) <  limit:
                curr_max = max(num,curr_max)
                curr_min = min(num,curr_min)
                len_curr += 1
            else:
                len_max = max(len_max,len_curr)
                curr_max = num # 下一个子数组当前最大值
                curr_min = num # 下一个子数组当前最小值
                len_curr = 1 # 因为该下标已经计算过一次 所以 设置当前子数组长度为 1
        return max(len_max,len_curr) # 当数组中所有数都满足条件 则len_max,len_curr 进行比较