描述
给定一个包含正整数的数组A , 以及两个正整数 L 和R (L <= R).
返回最大元素值在范围[L, R]之间的子数组(连续, 非空)的个数。
- L, R 和A[i]的范围在[0, 10^9]内.
- A的长度在 [1, 50000]内.
在线评测地址：领扣题库官网
样例1
输入: A = [2, 1, 4, 3], L = 2, R = 3
输出: 3
解释: 有三个子数组满足要求：[2], [2, 1], [3].样例2
输入: A = [7,3,6,7,1], L = 1, R = 4
输出: 2解题思路
一个子数组可以用一对下标 (l, r) 表示.
原本的数组可以视为被 大于R 的元素分割了, 因为大于R的元素下标必然不会在任一对合法的子数组内.
假定我们已经以 大于R 的元素将数组分割了, 那么现在我们考虑在一个不含大于R的元素的数组内, 如何求解答案:
运用容斥原理, 答案 = 所有子数组数量 - 不合法的子数组数量.
而不合法的子数组的数量就等于两个不小于L的元素之间的间隔部分的子数组数量, 就是相当于再以不小于L的元素分割, 这时得到的所有数组的全部子数组数量综合就是上面要减去的数量.
可以在一个循环内完成上述工作, 时间复杂度O(n), n是数组长度.
源代码
public class Solution {
/**
* @param A: an array
* @param L: an integer
* @param R: an integer
* @return: the number of subarrays such that the value of the maximum array element in that subarray is at least L and at most R
*/
public int numSubarrayBoundedMax(int[] A, int L, int R) {
int n = A.length;
if (n == 0) {
return 0;
}
int ans = 0;
for (int l = 0, r = 0; l < n; l++, r++) {
int maxv = A[r];
while (maxv <= R) { // 以大于R的元素为分割
r++;
if (r >= n) {
break;
}
maxv = Math.max(maxv, A[r]);
}
// 当前[l, r)范围的下标构成的子数组就是被大于R的元素分割出来的一段
ans += (r - l) * (r - l + 1) / 2; // 这一段的全体子数组的数量
int last = l - 1; // last表示上一个不小于L的元素的位置
for (; l < r; l++) { // 运用容斥原理把这一段内非法的再减去
if (A[l] >= L) { // 以.表示小于L的元素, 以#表示不小于L的元素, 例如 ..#..#..., 我们要减去的就是每一段连续的.含有的的子数组的数量和
ans -= (l - last) * (l - last - 1) / 2;
last = l;
}
}
ans -= (r - last) * (r - last - 1) / 2; // 不要忘记末尾还有一段
}
return ans;
}
}更多题解参考：九章官网solution
