Medium

题目描述

给你一个下标从 0 开始的整数数组 nums。如果 nums 的一个子数组满足以下条件，则称其为连续子数组：

设 i, i + 1, ..., j 是子数组中的下标。那么，对于每对下标 i <= i1, i2 <= j，都有 0 <= |nums[i1] - nums[i2]| <= 2。

返回连续子数组的总数。

子数组是数组中一个连续且非空的元素序列。

示例 1：

输入：nums = [5,4,2,4]
输出：8
解释：
长度为 1 的连续子数组：[5], [4], [2], [4]。
长度为 2 的连续子数组：[5,4], [4,2], [2,4]。
长度为 3 的连续子数组：[4,2,4]。
没有长度为 4 的连续子数组。
连续子数组总数 = 4 + 3 + 1 = 8。
可以证明不存在更多的连续子数组。

示例 2：

输入：nums = [1,2,3]
输出：6
解释：
长度为 1 的连续子数组：[1], [2], [3]。
长度为 2 的连续子数组：[1,2], [2,3]。
长度为 3 的连续子数组：[1,2,3]。
连续子数组总数 = 3 + 2 + 1 = 6。

提示：

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

解题思路

这是一道典型的滑动窗口问题。核心思路是使用双指针维护一个满足条件的窗口，窗口内任意两个元素的差值绝对值不超过2。

解题思路：

  1. 滑动窗口：维护左右指针，保证窗口内最大值与最小值的差不超过2
  2. 维护最值：可以使用双端队列（deque）或有序数据结构来维护窗口内的最大值和最小值
  3. 计数技巧：当窗口[left, right]满足条件时，以right为右端点的所有子数组都满足条件，数量为(right - left + 1)

具体算法：

  • 使用单调队列分别维护窗口内的最大值和最小值
  • 右指针扩展窗口，当窗口内最大值与最小值差值超过2时，收缩左边界
  • 每次右指针移动后，累加以当前位置为右端点的有效子数组数量

推荐解法：使用双端队列维护单调性，时间复杂度O(n)，空间复杂度O(n)。

也可以使用TreeMap/SortedMap等有序数据结构，但常数更大。

代码实现

class Solution {
public:
    long long continuousSubarrays(vector<int>& nums) {
        int n = nums.size();
        long long result = 0;
        int left = 0;
        
        deque<int> maxDeque, minDeque;
        
        for (int right = 0; right < n; 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 (!maxDeque.empty() && !minDeque.empty() && 
                   nums[maxDeque.front()] - nums[minDeque.front()] > 2) {
                if (maxDeque.front() == left) maxDeque.pop_front();
                if (minDeque.front() == left) minDeque.pop_front();
                left++;
            }
            
            // 以right为右端点的有效子数组数量
            result += right - left + 1;
        }
        
        return result;
    }
};

class Solution:
    def continuousSubarrays(self, nums: List[int]) -> int:
        from collections import deque
        
        n = len(nums)
        result = 0
        left = 0
        
        max_deque = deque()  # 单调递减队列，维护最大值
        min_deque = deque()  # 单调递增队列，维护最小值
        
        for right in range(n):
            # 维护单调递减队列（最大值）
            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 max_deque and min_deque and nums[max_deque[0]] - nums[min_deque[0]] > 2:
                if max_deque[0] == left:
                    max_deque.popleft()
                if min_deque[0] == left:
                    min_deque.popleft()
                left += 1
            
            # 以right为右端点的有效子数组数量
            result += right - left + 1
        
        return result

public class Solution {
    public long ContinuousSubarrays(int[] nums) {
        int n = nums.Length;
        long result = 0;
        int left = 0;
        
        LinkedList<int> maxDeque = new LinkedList<int>();
        LinkedList<int> minDeque = new LinkedList<int>();
        
        for (int right = 0; right < n; 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 (maxDeque.Count > 0 && minDeque.Count > 0 && 
                   nums[maxDeque.First.Value] - nums[minDeque.First.Value] > 2) {
                if (maxDeque.First.Value == left) maxDeque.RemoveFirst();
                if (minDeque.First.Value == left) minDeque.RemoveFirst();
                left++;
            }
            
            // 以right为右端点的有效子数组数量
            result += right - left + 1;
        }
        
        return result;
    }
}

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

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个元素最多进出双端队列一次
空间复杂度O(n)双端队列存储下标，最坏情况存储所有元素