795. 区间子数组个数#

题目描述#

给你一个整数数组 nums 和两个整数 left 和 right。返回**「好」子数组**的数量。

好子数组： 一个子数组，其中最大元素在范围 [left, right] 内（包含边界）。

即：子数组的最大值不小于 left，且不大于 right。

示例 1：

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

示例 2：

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

提示：

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

解题思路#

核心思想#

「最大元素在 [left, right] 内」等价于「子数组不含大于 right 的元素，且至少含一个大于等于 left 的元素」。

枚举每个右端点 i，统计以 i 结尾的好子数组个数再求和。为此需要两个关键位置：

lastGt：最近一个大于 right 的元素下标。以 i 结尾的合法子数组的左端点必须大于 lastGt（否则会引入超界元素）；
lastGe：最近一个大于等于 left 的元素下标。子数组左端点只要不大于 lastGe，就一定含有一个达标元素（保证最大值 ≥ left）。

于是以 i 结尾的好子数组数为：左端点可取 (lastGt, lastGe] 之间的整数，即 max(0, lastGe - lastGt)。

右端点扫描示意（nums=[2,9,2,5,6], left=2, right=8）：

1
i=0 x=2:  2<8 不超界，且 2>=2 → lastGe=0, lastGt=-1 → 贡献 0-(-1)=1 → [2]
2
i=1 x=9:  9>8 → lastGt=1, lastGe=0 → 贡献 max(0,0-1)=0
3
i=2 x=2:  2>=2 → lastGe=2, lastGt=1 → 贡献 2-1=1 → [2]
4
i=3 x=5:  5>=2 → lastGe=3, lastGt=1 → 贡献 3-1=2 → [2,5],[5]
5
i=4 x=6:  6>=2 → lastGe=4, lastGt=1 → 贡献 4-1=3 → [2,5,6],[5,6],[6]
6
总计 = 1+0+1+2+3 = 7

算法步骤#

初始化 ans = 0, lastGt = -1, lastGe = -1。
遍历每个元素 x = nums[i]：
- 若 x > right：更新 lastGt = i；
- 若 x >= left：更新 lastGe = i；
- ans += max(0, lastGe - lastGt)。
返回 ans。

逐步举例#

以题中示例 2 完整的贡献过程见上图，累计得 7。

再验证示例 1 nums=[2,1,4,3], left=2, right=3：

i	x	是否 >3	是否 ≥2	lastGt	lastGe	贡献
0	2	否	是	-1	0	1
1	1	否	否	-1	0	1
2	4	是	是	2	2	0
3	3	否	是	2	3	1

总计 1+1+0+1 = 3。

复杂度分析#

时间复杂度：O(N)，单次线性扫描。
空间复杂度：O(1)，只维护两个位置变量。

代码实现#

1
from typing import List
2

3

4
class Solution:
5
    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
6
        ans = 0
7
        last_gt = -1   # 最近一个 > right 的元素下标
8
        last_ge = -1   # 最近一个 >= left 的元素下标
9
        for i, x in enumerate(nums):
10
            if x > right:
11
                last_gt = i
12
            if x >= left:
13
                last_ge = i
14
            ans += max(0, last_ge - last_gt)
15
        return ans

1
import sys
2
from pathlib import Path
3

4
sys.path.insert(0, str(Path(__file__).parent))
5
import unittest
6

7
from solution import Solution
8

9

10
class TestSolution(unittest.TestCase):
11
    def test_example1(self):
12
        self.assertEqual(Solution().numSubarrayBoundedMax([2, 1, 4, 3], 2, 3), 3)
13

14
    def test_example2(self):
15
        self.assertEqual(Solution().numSubarrayBoundedMax([2, 9, 2, 5, 6], 2, 8), 7)
16

17

18
if __name__ == '__main__':
19
    unittest.main()