2444. 统计定界子数组的数目#

题目描述#

给你一个整数数组 nums 和两个整数 minK 以及 maxK。

nums 的定界子数组是满足下述条件之一的子数组：

子数组中的最小值等于 minK；
子数组中的最大值等于 maxK。

返回定界子数组的数目。

示例 1：

1
输入：nums = [1,3,5,2,7,5], minK = 1, maxK = 5
2
输出：2
3
解释：定界子数组是 [1,3,5] 和 [1,3,5,2]。

示例 2：

1
输入：nums = [1,1,1,1], minK = 1, maxK = 1
2
输出：10
3
解释：每个子数组都满足条件（最小值与最大值均为 1）。

提示：

2 <= nums.length <= 10^5
1 <= nums[i], minK, maxK <= 10^6

解题思路#

核心思想#

枚举每个右端点 i，统计「以 i 结尾且是定界子数组」的个数，再求和。

满足条件的子数组必须：

不含越界元素（< minK 或 > maxK）——记 bad 为最近一个越界元素下标，左端点必须 > bad；
同时包含最小值和最大值——记 mn 为最近一个等于 minK 的下标、mx 为最近一个等于 maxK 的下标。

若子数组左端点取 [bad+1, min(mn, mx)] 之间的任一值时，该区间的 [最小值,最大值] 都能恰好覆盖 minK 和 maxK 且不越界，因此都是定界子数组。个数为 max(0, min(mn, mx) - bad)。

右端点扫描示意（nums=[1,3,5,2,7,5], minK=1, maxK=5）：

1
i=0 x=1:  mn=0, mx=-1 → min=-1 → 贡献 max(0,-1-(-1))=0
2
i=1 x=3:  mn=0, mx=-1 → 贡献 0
3
i=2 x=5:  mn=0, mx=2  → min=0 → 贡献 max(0,0-(-1))=1 → [1,3,5]
4
i=3 x=2:  mn=0, mx=2  → min=0 → 贡献 max(0,0-(-1))=1 → [1,3,5,2]
5
i=4 x=7:  7>5 越界 → bad=4, mn=0, mx=2 → 贡献 max(0,0-4)=0
6
i=5 x=5:  mn=0, mx=5 → min=0 → 贡献 max(0,0-4)=0
7
总计 = 2

算法步骤#

初始化 ans = 0, bad = -1, mn = -1, mx = -1。
遍历每个 x = nums[i]：
- 若 x < minK or x > maxK：bad = i；
- 若 x == minK：mn = i；
- 若 x == maxK：mx = i；
- ans += max(0, min(mn, mx) - bad)。
返回 ans。

逐步举例#

以 nums=[1,1,1,1], minK=1, maxK=1 为例：

i	x	bad	mn	mx	min(mn,mx)-bad	贡献
0	1	-1	0	0	0-(-1)=1	1
1	1	-1	1	1	1-(-1)=2	2
2	1	-1	2	2	2-(-1)=3	3
3	1	-1	3	3	3-(-1)=4	4

总计 1+2+3+4 = 10，即所有 10 个子数组（n(n+1)/2）都满足条件。

复杂度分析#

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

代码实现#

1
from typing import List
2

3

4
class Solution:
5
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
6
        ans = 0
7
        bad = -1  # 最近一个越界（<minK 或 >maxK）的下标
8
        mn = -1   # 最近一个等于 minK 的下标
9
        mx = -1   # 最近一个等于 maxK 的下标
10
        for i, x in enumerate(nums):
11
            if x < minK or x > maxK:
12
                bad = i
13
            if x == minK:
14
                mn = i
15
            if x == maxK:
16
                mx = i
17
            ans += max(0, min(mn, mx) - bad)
18
        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().countSubarrays([1, 3, 5, 2, 7, 5], 1, 5), 2)
13

14
    def test_example2(self):
15
        self.assertEqual(Solution().countSubarrays([1, 1, 1, 1], 1, 1), 10)
16

17

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