区间子数组的个数【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]∈[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; } }
。复杂度
- 时间复杂度：O ( n 2 )
- 空间复杂度：O ( n 2 )
模拟
统计每个 nums[j] 作为子数组右端点时，所能贡献的子数组个数
- 思路：假设nums[j]∈[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]∈[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]∈[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; } }
。复杂度
- 时间复杂度：O ( n )
- 空间复杂度：O ( 1 )
单调栈
统计「每个 nums[i]作为子数组最大值时，所能贡献的子数组个数」
- 思路：统计所有最大值范围在[left,right]之间的子数组个数，可等价为统计每一个范围落在[left,right]之间的nums[i]作为最大值时子数组的个数。
- 实现：使用单调栈寻找每一个nums[i]左右最近一个比小于等于其的位置，分别记为L、R，那么对结果的贡献为(i−L)∗(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） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
