中等

问题描述

给你一个整数数组 nums 和两个整数：left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组，并返回满足条件的子数组的个数。

生成的测试用例保证结果符合 32-bit 整数范围。

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109
• 0 <= left <= right <= 109

双指针

使用两个指针 $low$ 和 $high$ 用于记录合适区间的两端。遍历数组，当某这个数字满足 $left \leq nums_i \leq right$ 时，$high$ 指针指向当前位置。当某个数字 $nums_i \gt right$ 时，需要 $low$ 指针指向当前位置， $high$ 指针重置为 $-1$，因为当前数字所构成的区间都不满足要求。每次遍历时，当 $high \neq -1$ 时，$(low, high]$ 区间都满足要求，子数组个数为 $high - low$。

/**
 * @param {number[]} nums
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
var numSubarrayBoundedMax = function (nums, left, right) {
  let low = -1
  let high = -1
  let ans = 0
  for (let i = 0; i < nums.length; ++i) {
    if (nums[i] >= left && nums[i] <= right) {
      high = i
    }
    if (nums[i] > right) {
      low = i
      high = -1
    }
    if (high !== -1) ans += high - low
  }
  return ans
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$