【每日一题Day37】LC795区间子数组的个数 | 单调栈 模拟

区间子数组的个数【LC795】

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

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

Given an integer array nums and two integers left and right, return the number of contiguous non-empty subarrays such that the value of the maximum array element in that subarray is in the range [left, right].

The test cases are generated so that the answer will fit in a 32-bit integer.

今天真的是精疲力竭的一天…数位dp还没做完明天继续做吧…好像单调栈也可以整理个合集了

暴力

• 思路：还是先用暴力理清思路，双重循环判断$nums[i,j]$是否符合条件[超时]

  • 当$nums[i,j-1]$符合条件时，只需要$nums[j]<right$即可
  • 当$nums[i,j-1]$不符合条件时，要求$nums[j]\in [left,right]$并且$nums[i,j-1]<left$

• 实现：需要使用标记判断上一个子数组是否符合条件，当$nums[j]>right$时，直接break

  class Solution {
      public int numSubarrayBoundedMax(int[] nums, int left, int right) {
          int len = nums.length; 
          int count = 0;
          for (int i = 0; i < len; i++){
              boolean preFlag = false;
              for (int j = i; j < len; j++){
                  if(nums[j] > right){
                      break;
                  }
                  if ( (preFlag && nums[j] <= right) || 
                      (!preFlag && nums[j] >= left && nums[j] <= right)){
                      preFlag= true;
                      count++;
                  } 
              }
          }
          return count;
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20

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

模拟

统计每个 nums[j] 作为子数组右端点时，所能贡献的子数组个数

• 思路：假设$nums[j]\in [left,right]$，$nums[i,j-1]<right$，区间$[i,j]$内符合条件的子数组个数即为以$nums[j]$为右端点、以$nums[i,j]$为左端点的连续子数组个数，符合条件的连续子数组个数为$j-i+1$，对于新到来的$nums[j+1]$有三种情况

  • $nums[j+1]$小于$left$，那么其对结果的贡献仍为$j-i+1$，右端点为$nums[j+1]$，左端点在$[i,j]$内
  • $nums[j+1]\in [left,right]$，那么其对结果的贡献为$j+1-i+1$，右端点为$nums[j+1]$，左端点在$[i,j+1]$内
  • $nums[j+1]$大于$right$那么其不会增加新的符合条件的连续子数组，其对结果的贡献为$0$，从下一个下标开始重新寻找符合条件的$num$

• 实现：使用变量记录上一个大于$right$的坐标$k$，每遍历一个$num[i]$，如果在该区间$[k+1,i]$内存在$nums[j]\in [left,right]$，那么其对结果的贡献为$j-k$，注意$j$为该区间内区间$[k+1,i]$最新即最大的符合条件的下标

  class Solution {
      public int numSubarrayBoundedMax(int[] nums, int left, int right) {
          int len = nums.length; 
          int lastBiggerR = -1;
          int lastIn = -1;
          int count = 0;
          for (int i = 0; i < len; i++){
              if (nums[i] >= left && nums[i] <= right ){
                  lastIn = i;
              }else if (nums[i] > right){
                  lastBiggerR = i;
                  lastIn = -1;
              }
              if (lastIn != -1){
                  count += lastIn - lastBiggerR;
              }
          }
          return count;
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20

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

单调栈

统计「每个 nums[i]作为子数组最大值时，所能贡献的子数组个数」

• 思路：统计所有最大值范围在 $[left,right]$之间的子数组个数，可等价为统计每一个范围落在$[left,right]$之间的$nums[i]$作为最大值时子数组的个数。

• 实现：使用单调栈寻找每一个 $nums[i]$左右最近一个比小于等于其的位置，分别记为$L、R$，那么对结果的贡献为$(i-L)\ast (b-R)$，累加返回最终结果

  class Solution {
      public int numSubarrayBoundedMax(int[] nums, int a, int b) {
          int n = nums.length, ans = 0;
          int[] l = new int[n + 10], r = new int[n + 10];
          Arrays.fill(l, -1); Arrays.fill(r, n);
          Deque<Integer> d = new ArrayDeque<>();
          for (int i = 0; i < n; i++) {
              while (!d.isEmpty() && nums[d.peekLast()] < nums[i]) r[d.pollLast()] = i;
              d.addLast(i);
          }
          d.clear();
          for (int i = n - 1; i >= 0; i--) {
              while (!d.isEmpty() && nums[d.peekLast()] <= nums[i]) l[d.pollLast()] = i;
              d.addLast(i);
          }
          for (int i = 0; i < n; i++) {
              if (nums[i] < a || nums[i] > b) continue;
              ans += (i - l[i]) * (r[i] - i);
          }
          return ans;
      }
  }
  
  作者：宫水三叶
  链接：https://leetcode.cn/problems/number-of-subarrays-with-bounded-maximum/solutions/1988320/by-ac_oier-gmpt/
  来源：力扣（LeetCode）
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27