給定一個(gè)包含正整數(shù)的數(shù)組A , 以及兩個(gè)正整數(shù) L 和R (L <= R).
返回最大元素值在范圍[L, R]之間的子數(shù)組(連續(xù), 非空)的個(gè)數(shù),
number-of-subarrays-with-bounded-maximum
樣例
樣例 1:
輸入: A = [2, 1, 4, 3], L = 2, R = 3
輸出: 3
解釋: 有三個(gè)子數(shù)組滿足要求：[2], [2, 1], [3].
樣例 2:
輸入: A = [7,3,6,7,1], L = 1, R = 4
輸出: 2
思路1 O(N^2)、遍歷數(shù)組 設(shè)置一個(gè) max 值，在遍歷數(shù)組 取出最大值，如果當(dāng)前 a[j] > r 跳出循環(huán)，如果 a[j] >== l result++, 整體思想有點(diǎn) dp 的感覺(jué)
思路2 O(N)、遍歷數(shù)組，記錄下符合位置的索引 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;
}
}
