给定一个包含正整数的数组A , 以及两个正整数 L 和R (L <= R).
返回最大元素值在范围[L, R]之间的子数组(连续, 非空)的个数,
number-of-subarrays-with-bounded-maximum
样例
样例 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
思路1 O(N^2)、遍历数组 设置一个 max 值，在遍历数组 取出最大值，如果当前 a[j] > r 跳出循环，如果 a[j] >== l result++, 整体思想有点 dp 的感觉
思路2 O(N)、遍历数组，记录下符合位置的索引 index ，和不符合位置的索引 temp ，result += index - temp
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) {
// Write your code here
int result = 0;
for (int i = 0; i < a.length; i++) {
int max = Integer.MIN_VALUE;
for (int j = i; j < a.length; j++) {
max = Math.max(max, a[j]);
if (max > r) {
break;
}
if (max >= l) {
result++;
}
}
}
return result;
}
}
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) {
// Write your code here
int result = 0;
int index = -1;
int temp = -1;
for (int i = 0; i < a.length; i++) {
if (a[i] > r) {
index = temp = i;
continue;
}
if (a[i] >= l) {
index = i;
}
result += index - temp;
}
return result;
}
}
