Java实现 LeetCode 795 区间子数组个数 （暴力分析）数据结构与算法南 墙-

795. 区间子数组个数

给定一个元素都是正整数的数组A ，正整数 L 以及 R (L <= R)。

求连续、非空且其中最大元素满足大于等于L 小于等于R的子数组个数。

例如 :
输入:
A = [2, 1, 4, 3]
L = 2
R = 3
输出: 3
解释: 满足条件的子数组: [2], [2, 1], [3].
注意:

L, R 和 A[i] 都是整数，范围在 [0, 10^9]。
数组 A 的长度范围在[1, 50000]。

PS：
大佬简单易懂的代码，
下面有我写的那个，不过效率又低，又难懂
枉我在那疯狂写了半天，效率还低，唉

class Solution { public int numSubarrayBoundedMax(int[] A, int L, int R) { // 最大元素满足大于等于L小于等于R的子数组个数 = 最大元素小于等于R的子数组个数 - 最大元素小于L的子数组个数 return numSubarrayBoundedMax(A, R) - numSubarrayBoundedMax(A, L - 1); } private int numSubarrayBoundedMax(int[] A, int Max) { int res = 0; int numSubarry = 0; for (int num : A) { if (num <= Max) {                 numSubarry++;                 res += numSubarry; } else {                 numSubarry = 0; } } return res; } } 

class Solution { public int numSubarrayBoundedMax(int[] A, int L, int R) { int len = A.length; int all = len * (len + 1) / 2; int maxL = all - numMin(A, L); int maxR = all - numMin(A, R + 1); return maxL - maxR; } public int numMin(int[] nums, int min) { int sum = 0; int left = 0; while(left < nums.length) { while (left < nums.length && nums[left] >= min) {        left++; } int right = left; while (right < nums.length && nums[right] < min) {        right++; } int gap = right - left;       sum += gap * (gap + 1) / 2;             left = right; } return sum; } }