[leetcode/lintcode 题解] 算法面试真题详解：最大值在界内的子

描述
给定一个包含正整数的数组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 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 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

本文转自网络，原文链接：https://developer.aliyun.com/article/783806
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！