:-: 1.6 区间子数组个数 ***** **题干：** 给定一个元素都是正整数的数组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]。 ``` **题目分析：** 题目要求求连续、非空且其中最大元素满足大于等于L 小于等于R的子数组个数：根据条件 L 与 R ,可以把数字分为三种，分别是 < L，>= L 且 <= R 以及 > R。其中 > R 的数据不可能存在与符合条件（最大元素在 L R 之间）的子数组中，所以我们可以把 > R 的数据当作分界线（这些数字是不可能出现在子数组中的），而在子数组中< L的数字允许存在，但不允许单独此类数字单独存在，子数组中至少有一个>= L 且 <= R的数，而>= L 且 <= R的数可单独存在作为一个子数组。也就是说由这几种情况出现：当A = [2,1,4,3]，L= 2，R = 3时满足条件的子数组为[2]， [2, 1]，[3]；当A = [4,5,6]，L = 2，R = 8时满足条件的子数组为[4]，[5]，[6]，[45]，[46]，[56]；当A = [2,1,1,3]，L = 2，R = 3时满足条件的子数组为[2]，[2,1]，[2,1,1]，[2,1,1,3]，[1,1,3]，[1,3]，[3]；通过分析发现 < L的数字参与子数组必须依附于其中必须有 >= L 且 <= R 的数字，而子数组中数字全部满足 >= L 且 <= R 的数字，不受限制，想怎么结合怎么结合，但必须连续。 **新手有可能遇到的解题思路陷阱：** 1.纠结于求介于（L，R）之间的最大值，这是个可有可无的条件，因为每个介于（L，R）之间的数字都有可能是最大值（如若L = 2，R = 8，满足条件的子数组 = [5,6,7]，则5在此满足条件的子集中也是最大值）。2.顾尾不顾头，使用双指针法（滑动窗口法）时容易忽略首个数字位置从零开始，从而忽略掉。3.忽略连续这个条件，以为求非空真子集。 **解题思路分析以及代码实现：** 第一种思路：暴力破解 第一种思路代码： ``` public int numSubarrayBoundedMax(int[] A, int L, int R) { int count = 0; for (int i = 0; i < A.length; i++) { int big = A[i]; for (int j = i; j < A.length; j++) { big = Math.max(big, A[j]); if (big >= L && big <= R) count++; } } return count; } ``` **复杂度分析** 时间复杂度：O(n^2)。 空间复杂度：O(1)。 第一种思路代码：暴力破解，标记前方是否有符合的数字出现有就一直累加，直到有 > R的数字出现，作为分割线。 ``` public int numSubarrayBoundedMax(int[] A, int L, int R) { int res = 0; for (int i = 0; i < A.length; i++) { int num = 0; boolean flag = false; for (int j = i; j < A.length; j++) { if (A[j] > R) { break; } else if (A[j] < L) { if (flag) { res++; } } else { res++; flag = true; } } } return res; } ``` **复杂度分析** 时间复杂度：O(n^2)。 空间复杂度：O(1)。 第二种思路代码：双指针法（滑动窗口法），遇到连续都属于 >= L 且 <= R 的数字，可作等差数列（a1 = 1，d = 1）,连续连续都属于 < L的数字且在此之前连续跟有 >= L 且 <= R 的数字，则可作为等比数列（a1 = 1，q = 1），遇到 > R的数字则重新开始，双指针统一位置。如果更加节省时间，我们可以使用continue，但是再此之前双指针要进行重置，避免执行下面的判断，影响时间。 第二种思路代码： ``` public int numSubarrayBoundedMax(int[] A, int L, int R) { int result = 0, left = -1, right = -1; for (int i = 0; i < A.length; i++) { /*if (A[i] > R) { left = i; right = i; continue; }*/ if (A[i] > R) left = i; if (A[i] >= L) right = i; result += right - left; } return result; } ``` **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(1)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**