0795. Number of Subarrays with Bounded Maximum

题目信息

题号:

0795

难度:

Medium

主题:

数组、连续子数组、最大值范围

原题:

LeetCode 0795

重点:

统计非空连续子数组,条件只要求子数组最大值落在闭区间 [left, right];数组中小于 left 的元素可以包含在合法子数组中

题目重述

给定整数数组 nums 和两个整数 left、right,其中 left <= right。请统计有多少个非空连续子数组满足:该子数组中的最大元素位于闭区间 [left, right] 内。

子数组必须由原数组中一段连续元素组成。子数组可以包含小于 left 的元素,只要至少存在一个元素使最大值不小于 left,并且所有元素都不大于 right。

1 <= nums.length <= 10^5,0 <= nums[i] <= 10^9,0 <= left <= right <= 10^9。答案保证在 32 位有符号整数范围内。

自建示例

大于上界的元素会截断可选范围:

输入:nums = [1,2,2,5,3], left = 2, right = 3
输出:6
解释:前半段 [1,2,2] 中有五个最大值为 2 的子数组:[1,2]、[1,2,2]、第一个 [2]、[2,2]、第二个 [2];末尾 [3] 也合法。元素 5 大于上界,任何包含它的子数组都不合法。

所有元素都低于下界:

输入:nums = [1,1], left = 2, right = 3
输出:0
解释:三个非空连续子数组分别是两个单元素 [1] 和 [1,1],它们的最大值都为 1,小于下界 2,因此没有合法子数组。