Medium

题目描述

给你一个整数数组 nums 和一个整数 k。

对于任意子数组 nums[l..r]，定义其花费为：

cost = (max(nums[l..r]) - min(nums[l..r])) * (r - l + 1)

返回一个整数，表示 nums 中花费小于等于 k 的子数组数目。

示例 1：

输入：nums = [1,3,2], k = 4
输出：5
解释：
我们考虑 nums 的所有子数组：
- nums[0..0]：cost = (1 - 1) * 1 = 0
- nums[0..1]：cost = (3 - 1) * 2 = 4  
- nums[0..2]：cost = (3 - 1) * 3 = 6
- nums[1..1]：cost = (3 - 3) * 1 = 0
- nums[1..2]：cost = (3 - 2) * 2 = 2
- nums[2..2]：cost = (2 - 2) * 1 = 0

有 5 个子数组的花费小于等于 4。

示例 2：

输入：nums = [5,5,5,5], k = 0
输出：10
解释：
对于 nums 的任意子数组，最大值和最小值相同，所以花费总是 0。
因此，nums 的每个子数组花费都小于等于 0。
对于长度为 4 的数组，子数组总数为 (4 * 5) / 2 = 10。

示例 3：

输入：nums = [1,2,3], k = 0
输出：3
解释：
nums 中花费为 0 的子数组只有单元素子数组，共 3 个。

约束条件：

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

解题思路

这道题需要统计所有花费不超过 k 的子数组数目。核心思路是使用滑动窗口配合单调双端队列来高效维护窗口内的最大值和最小值。

解题步骤：

  1. 滑动窗口思想：对于每个右端点 r，找到最远的左端点 l，使得子数组 [l, r] 的花费不超过 k。那么以 r 为右端点的所有合法子数组数目为 r - l + 1。

  2. 单调队列优化：

    • 使用一个单调递减队列维护窗口内的最大值
    • 使用一个单调递增队列维护窗口内的最小值
    • 当窗口花费超过 k 时，缩小左边界

  3. 花费计算：每次扩展右边界时，计算当前窗口的花费，如果超过 k，就移动左边界直到满足条件。

  4. 计数策略：当窗口 [l, r] 合法时，以 r 为右端点的所有合法子数组有 r - l + 1 个。

时间复杂度为 O(n)，因为每个元素最多进出队列一次。空间复杂度为 O(n)，用于存储单调队列。

代码实现

class Solution {
public:
    long long countSubarrays(vector<int>& nums, long long k) {
        int n = nums.size();
        deque<int> maxDeque, minDeque;
        long long result = 0;
        int left = 0;
        
        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 (left <= right) {
                long long maxVal = nums[maxDeque.front()];
                long long minVal = nums[minDeque.front()];
                long long cost = (maxVal - minVal) * (right - left + 1);
                
                if (cost <= k) {
                    break;
                }
                
                // 移除过期元素
                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 countSubarrays(self, nums: List[int], k: int) -> int:
        from collections import deque
        
        n = len(nums)
        max_deque = deque()  # 单调递减队列维护最大值
        min_deque = deque()  # 单调递增队列维护最小值
        result = 0
        left = 0
        
        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 left <= right:
                max_val = nums[max_deque[0]]
                min_val = nums[min_deque[0]]
                cost = (max_val - min_val) * (right - left + 1)
                
                if cost <= k:
                    break
                
                # 移除过期元素
                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 CountSubarrays(int[] nums, long k) {
        int n = nums.Length;
        var maxDeque = new LinkedList<int>(); // 单调递减队列维护最大值
        var minDeque = new LinkedList<int>(); // 单调递增队列维护最小值
        long result = 0;
        int left = 0;
        
        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 (left <= right) {
                long maxVal = nums[maxDeque.First.Value];
                long minVal = nums[minDeque.First.Value];
                long cost = (maxVal - minVal) * (right - left + 1);
                
                if (cost <= k) {
                    break;
                }
                
                // 移除过期元素
                if (maxDeque.First.Value == left) {
                    maxDeque.RemoveFirst();
                }
                if (minDeque.First.Value == left) {
                    minDeque.RemoveFirst();
                }
                left++;
            }
            
            // 统计以right为右端点的合法子数组数目
            result += right - left + 1;
        }
        
        return result;
    }
}

var countSubarrays = function(nums, k) {
    let count = 0;
    let n = nums.length;
    
    for (let i = 0; i < n; i++) {
        let min = nums[i];
        let max = nums[i];
        
        for (let j = i; j < n; j++) {
            min = Math.min(min, nums[j]);
            max = Math.max(max, nums[j]);
            
            let cost = (max - min) * (j - i + 1);
            
            if (cost <= k) {
                count++;
            } else {
                break;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间复杂度O(n)
空间复杂度O(n)
  • 时间复杂度：O(n)，每个元素最多进出单调队列一次
  • 空间复杂度：O(n)，单调队列在最坏情况下存储所有元素