LC-795.区间子数组个数

题目描述

leetcode 中等题

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

示例1：

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

提示1：

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

双指针

显然符合题意的子数组必然不包含任意的 $nums[i] > right$，并且必须包含一个 $left <= nums[i] <= right$。

我们初始化左右指针都指向 $0$ ，右指针每次后移一位。并统计以右指针为子数组右端点且符合题意的子数组个数。

具体遍历时，分以下三种情况进行处理

• 如果当前元素 $left <= nums[i] <= right$，我们只需要将答案累加 $rightPoint - leftPoint + 1$ 即可。并且同时维护一个 $lastMatch$，代表最后一个遇到的符合大于 $left$ 小于 $right$ 的元素下标，将其更新为当前下标。
• 如果当前元素 $nums[i] < left$ ，我们就需要找到左边第一个满足 $left <= nums[i] <= right$ 的下标，也就是 $lastMatch$，则显然以 $[lastMatch…rightPoint]$ 段任意元素作为左端点的子数组都不符合要求；而对于 $[leftPoint…lastMatch]$ 段，每个子数组都至少存在一个 $lastMatch$ 是符合要求的，所以我们将答案累加 $lastMatch - leftPoint + 1$ 。
• 如果当前元素 $nums > right$ ，我们只需要将左指针移动到 $i + 1$ 并将 $lastMatch$ 置为 $-1$ 即可，因为包含该元素的任意子数组都不符合题目要求。

  class Solution {
      public int numSubarrayBoundedMax(int[] nums, int left, int right) {
          int ans = 0, lastMatch = -1, n = nums.length;
          for(int leftPoint = 0, rightPoint = 0; rightPoint < n; rightPoint++){
              if(left <= nums[rightPoint]  && nums[rightPoint] <= right){
                  lastMatch = rightPoint;
              }
              if(nums[rightPoint] > right){
                  lastMatch = -1;
                  leftPoint = rightPoint + 1;
              }
              if(lastMatch != - 1){
                  ans += lastMatch - leftPoint + 1;
              }
          }
          return ans;
      }
  }

单调栈

前面双指针的做法相当于每次求解以遍历到的当前元素作为右端点的合法子数组数量，另一种方法则是求解以当前元素作为子数组最大值的合法子数组数量。

容易想到，我们利用单调栈维护出每个元素左边第一个大于当前元素的下标 $left[i]$、右边第一个大于当前元素的下标 $right[i]$。

那么该范围内以该元素作为子数组最大值的数量就等价于包含该元素的子数组数量，也就是 $(i - left[i]) \times (right[i] - i)$。

需要注意的是，由于数组中存在重复元素，我们在找第一个大于当前元素的下标时，可能存在每个重复元素都越过了彼此，由此产生重复统计。所以我们可以将某一侧的条件改为大于等于，实现类似半闭半开的效果。

class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        int n = nums.length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        Deque<Integer> monoStack = new ArrayDeque<>();
        for(int i = 0; i < n; i++){
            while(!monoStack.isEmpty() && nums[i] >= nums[monoStack.peekLast()]){
                monoStack.pollLast();
            }
            leftMax[i] =monoStack.isEmpty() ? -1 : monoStack.peekLast();
            monoStack.offerLast(i);
        }
        monoStack.clear();
        for(int i = n - 1; i >= 0; i--){
            while(!monoStack.isEmpty() && nums[i] > nums[monoStack.peekLast()]){
                monoStack.pollLast();
            }
            rightMax[i] = monoStack.isEmpty() ? n : monoStack.peekLast();
            monoStack.offerLast(i);
        }
        int ans = 0;
        for(int i = 0; i < n; i++){
            if(nums[i] > right || nums[i] < left){
                continue;
            }
            ans += (i - leftMax[i]) * (rightMax[i] - i);
        }
        return ans;
    }
}