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 位有符号整数范围内。 自建示例 -------- 大于上界的元素会截断可选范围: .. code-block:: text 输入: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 大于上界,任何包含它的子数组都不合法。 所有元素都低于下界: .. code-block:: text 输入:nums = [1,1], left = 2, right = 3 输出:0 解释:三个非空连续子数组分别是两个单元素 [1] 和 [1,1],它们的最大值都为 1,小于下界 2,因此没有合法子数组。