Medium

题目描述

给你一个整数数组 nums 和两个整数 left 和 right ，返回连续、非空且其中最大元素在范围 [left, right] 内的子数组个数。

测试用例的答案保证符合 32-bit 整数范围。

示例 1：

输入：nums = [2,1,4,3], left = 2, right = 3
输出：3
解释：满足条件的三个子数组：[2], [2, 1], [3]

示例 2：

输入：nums = [2,9,2,5,6], left = 2, right = 8
输出：7

提示：

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

解题思路

这道题要求计算最大值在指定区间内的子数组个数。关键思路是转换问题：将原问题转化为两个更简单的问题相减。

核心思想：

  • f(bound) = 最大值 ≤ bound 的子数组个数
  • 答案 = f(right) - f(left-1)

这样就将"最大值在[left,right]内"转化为"最大值≤right 且 最大值≥left"的问题。

具体实现： 对于计算最大值 ≤ bound 的子数组个数，使用双指针法：

  1. 维护左指针 start，右指针遍历数组
  2. 当遇到 nums[i] > bound 时，重置 start = i + 1
  3. 否则，以位置 i 结尾的合法子数组有 i - start + 1 个

时间复杂度优化： 也可以用一次遍历的方法：维护三个指针分别记录上一个超过right的位置、上一个在[left,right]内的位置，直接计算贡献。

推荐解法： 转换问题 + 双指针，思路清晰易懂。

代码实现

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
        return atMost(nums, right) - atMost(nums, left - 1);
    }
    
private:
    int atMost(vector<int>& nums, int bound) {
        int result = 0, start = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > bound) {
                start = i + 1;
            } else {
                result += i - start + 1;
            }
        }
        return result;
    }
};

class Solution:
    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
        def atMost(bound):
            result = start = 0
            for i, num in enumerate(nums):
                if num > bound:
                    start = i + 1
                else:
                    result += i - start + 1
            return result
        
        return atMost(right) - atMost(left - 1)

public class Solution {
    public int NumSubarrayBoundedMax(int[] nums, int left, int right) {
        return AtMost(nums, right) - AtMost(nums, left - 1);
    }
    
    private int AtMost(int[] nums, int bound) {
        int result = 0, start = 0;
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] > bound) {
                start = i + 1;
            } else {
                result += i - start + 1;
            }
        }
        return result;
    }
}

var numSubarrayBoundedMax = function(nums, left, right) {
    const atMost = (bound) => {
        let result = 0, start = 0;
        for (let i = 0; i < nums.length; i++) {
            if (nums[i] > bound) {
                start = i + 1;
            } else {
                result += i - start + 1;
            }
        }
        return result;
    };
    
    return atMost(right) - atMost(left - 1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，需要遍历数组两次
空间复杂度O(1)，只使用常数额外空间

相关题目