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.
Example 1:
Input: nums = [2,1,4,3], left = 2, right = 3
Output: 3
Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].
Example 2:
Input: nums = [2,9,2,5,6], left = 2, right = 8
Output: 7
Constraints:
1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9
0 <= left <= right <= 10^9
这题一开始审错题了，还以为是subarray的和在range里。后来看了半天，原来是subarray里max的元素在range里。然后，就想到用cnt>=right的减去cnt>=（left-1）的。T:O(n),S:O(1)。这里因为我用了（n + 1）* n / 2的方法，所以要long，不然会越界。看了答案，发现一直没掌握好这种直接加的方法。抄了一遍。有一丢丢像,跟two sum里那种一次加一堆的也有一丢丢像。另外一个是
// 更简单的写法
public int numSubarrayBoundedMax(int[] nums, int left, int right) {
if (nums == null || nums.length == 0 || left > right) {
return -1;
}
int lessThanLeft = cntMaxElemLessOrEqualToK(nums, left - 1);
int lessThanRight = cntMaxElemLessOrEqualToK(nums, right);
return lessThanRight - lessThanLeft;
}
private int cntMaxElemLessOrEqualToK(int[] nums, int k) {
int curLen = 0;
int cnt = 0;
for (int i = 0; i < nums.length; i++) {
curLen = nums[i] <= k ? curLen + 1 : 0;
cnt = cnt + curLen;
}
return cnt;
}
// (n + 1) * n / 2，越界的方法
public int numSubarrayBoundedMax(int[] nums, int left, int right) {
if (nums == null || nums.length == 0 || left > right) {
return -1;
}
long lessThanLeft = cntMaxElemLessOrEqualToK(nums, left - 1);
long lessThanRight = cntMaxElemLessOrEqualToK(nums, right);
return (int) (lessThanRight - lessThanLeft);
}
private long cntMaxElemLessOrEqualToK(int[] nums, int k) {
int left = 0;
long cnt = 0;
for (int right = 0; right <= nums.length; right++) {
if (right == nums.length || nums[right] > k) {
long n = right - left;
cnt = cnt + (n + 1) * n / 2;
left = right + 1;
}
}
return cnt;
}