Medium

题目描述

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

解题思路

这道题要求找到最长的连续子数组，使得其中任意两个元素的绝对差不超过限制值。关键观察是：子数组中任意两个元素的最大绝对差等于子数组的最大值与最小值的差。

因此，问题转化为：找到最长的子数组，使得 max - min <= limit。

解法思路：

  1. 滑动窗口 + 单调双端队列（推荐）：使用两个双端队列分别维护窗口内的最大值和最小值。当窗口不满足条件时，收缩左边界。

  2. 滑动窗口 + 有序集合：使用 multiset 等数据结构维护窗口内元素的有序性，可以快速获取最值。

  3. 滑动窗口 + 堆：使用大顶堆和小顶堆分别维护最大值和最小值，但需要处理过期元素。

单调队列解法详解：

  • 使用递减单调队列维护最大值：队首始终是窗口内的最大值
  • 使用递增单调队列维护最小值：队首始终是窗口内的最小值
  • 当最大值与最小值的差超过 limit 时，移动左指针并更新队列
  • 时间复杂度 O(n)，空间复杂度 O(n)

这种方法效率最高，因为每个元素最多入队出队各一次。

代码实现

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        deque<int> maxDeque; // 维护最大值的递减队列
        deque<int> minDeque; // 维护最小值的递增队列
        int left = 0, maxLen = 0;
        
        for (int right = 0; right < nums.size(); right++) {
            // 维护递减队列（最大值队列）
            while (!maxDeque.empty() && nums[maxDeque.back()] <= nums[right]) {
                maxDeque.pop_back();
            }
            maxDeque.push_back(right);
            
            // 维护递增队列（最小值队列）
            while (!minDeque.empty() && nums[minDeque.back()] >= nums[right]) {
                minDeque.pop_back();
            }
            minDeque.push_back(right);
            
            // 如果当前窗口不满足条件，收缩左边界
            while (nums[maxDeque.front()] - nums[minDeque.front()] > limit) {
                if (maxDeque.front() == left) {
                    maxDeque.pop_front();
                }
                if (minDeque.front() == left) {
                    minDeque.pop_front();
                }
                left++;
            }
            
            maxLen = max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
};

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        from collections import deque
        
        max_deque = deque()  # 维护最大值的递减队列
        min_deque = deque()  # 维护最小值的递增队列
        left = 0
        max_len = 0
        
        for right in range(len(nums)):
            # 维护递减队列（最大值队列）
            while max_deque and nums[max_deque[-1]] <= nums[right]:
                max_deque.pop()
            max_deque.append(right)
            
            # 维护递增队列（最小值队列）
            while min_deque and nums[min_deque[-1]] >= nums[right]:
                min_deque.pop()
            min_deque.append(right)
            
            # 如果当前窗口不满足条件，收缩左边界
            while nums[max_deque[0]] - nums[min_deque[0]] > limit:
                if max_deque[0] == left:
                    max_deque.popleft()
                if min_deque[0] == left:
                    min_deque.popleft()
                left += 1
            
            max_len = max(max_len, right - left + 1)
        
        return max_len

public class Solution {
    public int LongestSubarray(int[] nums, int limit) {
        var maxDeque = new LinkedList<int>(); // 维护最大值的递减队列
        var minDeque = new LinkedList<int>(); // 维护最小值的递增队列
        int left = 0, maxLen = 0;
        
        for (int right = 0; right < nums.Length; right++) {
            // 维护递减队列（最大值队列）
            while (maxDeque.Count > 0 && nums[maxDeque.Last.Value] <= nums[right]) {
                maxDeque.RemoveLast();
            }
            maxDeque.AddLast(right);
            
            // 维护递增队列（最小值队列）
            while (minDeque.Count > 0 && nums[minDeque.Last.Value] >= nums[right]) {
                minDeque.RemoveLast();
            }
            minDeque.AddLast(right);
            
            // 如果当前窗口不满足条件，收缩左边界
            while (nums[maxDeque.First.Value] - nums[minDeque.First.Value] > limit) {
                if (maxDeque.First.Value == left) {
                    maxDeque.RemoveFirst();
                }
                if (minDeque.First.Value == left) {
                    minDeque.RemoveFirst();
                }
                left++;
            }
            
            maxLen = Math.Max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
}

var longestSubarray = function(nums, limit) {
    let left = 0;
    let maxLen = 0;
    let maxDeque = [];
    let minDeque = [];
    
    for (let right = 0; right < nums.length; right++) {
        while (maxDeque.length && nums[maxDeque[maxDeque.length - 1]] <= nums[right]) {
            maxDeque.pop();
        }
        maxDeque.push(right);
        
        while (minDeque.length && nums[minDeque[minDeque.length - 1]] >= nums[right]) {
            minDeque.pop();
        }
        minDeque.push(right);
        
        while (nums[maxDeque[0]] - nums[minDeque[0]] > limit) {
            if (maxDeque[0] === left) maxDeque.shift();
            if (minDeque[0] === left) minDeque.shift();
            left++;
        }
        
        maxLen = Math.max(maxLen, right - left + 1);
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度单调队列解法
时间复杂度O(n)
空间复杂度O(n)

说明：

  • 时间复杂度：每个元素最多入队和出队各一次，总体为 O(n)
  • 空间复杂度：两个单调队列最多存储 O(n) 个元素

相关题目