JAVA 牛牛

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

  • May 05, 2020
  • 0 views
  • 难度：中等
  • 本题涉及算法： 滑动窗口
  • 思路： 滑动窗口
  • 类似题型:

题目 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

方法一 滑动窗口

解题思路

  1. 维护一直最大值和最小值

  2. 维护一个最长数组 \(sub\_nums增加的条件=\begin{cases} abs(num - curr\_max) <= limit & 判断当前元素是否复合条件，当前元素和数组中最大元素比较\\ abs(num - curr\_min) <= limit & 判断当前元素是否复合条件，当前元素和数组中最小元素比较 \\ abs(curr\_max - curr\_min) <= limit & 判断数组中元素是否符合条件，数组中最大元素和最小元素比较 \end{cases}\)

  3. 当不复合数组增加条件，则以当前长度向后移动
  4. 在向后移动的同时，数组中元素也在在发生变化，所以需要更新数组中的最大最小值

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

pic

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 进行比较
Search