LeetCode 795. 区间子数组个数

Categories:

题目描述
思路分析
1. 解法一：区间计数转化（推荐）
相似题目

题目描述

✅ 795. 区间子数组个数

思路分析

解法一：区间计数转化（推荐）

核心思路：

统计最大值 <= R 的子数组数量为 count(R)。

统计最大值 <= L-1 的子数组数量为 count(L-1)。

答案为 count(R) - count(L-1)。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)。

class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        return count(nums, right) - count(nums, left - 1);
    }

    private int count(int[] nums, int bound) {
        int cur = 0;
        int total = 0;

        for (int num : nums) {
            if (num <= bound) {
                cur++;
            } else {
                cur = 0;
            }
            total += cur;
        }

        return total;
    }
}

func numSubarrayBoundedMax(nums []int, left int, right int) int {
	return countBound(nums, right) - countBound(nums, left-1)
}

func countBound(nums []int, bound int) int {
	cur := 0
	total := 0

	for _, num := range nums {
		if num <= bound {
			cur++
		} else {
			cur = 0
		}
		total += cur
	}

	return total
}

相似题目

题目	难度	考察点
1248. 统计「优美子数组」	中等	计数
930. 和相同的二元子数组	中等	前缀和
209. 长度最小的子数组	中等	双指针
713. 乘积小于 K 的子数组	中等	双指针
560. 和为K的子数组	中等	前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/51282374