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

简介: [leetcode/lintcode 题解] 算法面试真题详解:最大值在界内的子数组个数

描述
给定一个包含正整数的数组A , 以及两个正整数 L 和R (L <= R).
返回最大元素值在范围[L, R]之间的子数组(连续, 非空)的个数。

  1. L, R 和A[i]的范围在[0, 10^9]内.
  2. 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 < n; 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 < r; 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

相关文章
|
开发者 索引 Python
这些年背过的面试题——LeetCode
本文是技术人面试系列LeetCode篇,一文带你详细了解,欢迎收藏!
|
算法 Python
【Leetcode刷题Python】子数组查找
一个用于寻找给定字符串中最长重复子串的Python函数实现,采用了滑动窗口的方法来检测重复的子串。
204 1
|
算法 测试技术 程序员
力扣经典150题第三十题:长度最小的子数组
力扣经典150题第三十题:长度最小的子数组
297 1
|
SQL 算法 大数据
深入解析力扣176题:第二高的薪水(子查询与LIMIT详解及模拟面试问答)
深入解析力扣176题:第二高的薪水(子查询与LIMIT详解及模拟面试问答)
|
算法 数据挖掘 大数据
深入解析力扣172题:阶乘后的零(计算因子5的方法详解及模拟面试问答)
深入解析力扣172题:阶乘后的零(计算因子5的方法详解及模拟面试问答)
|
算法 数据挖掘 大数据
深入解析力扣171题:Excel表列序号(进制转换法详解及模拟面试问答)
深入解析力扣171题:Excel表列序号(进制转换法详解及模拟面试问答)
|
算法 Java
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
366 0
|
算法 Python
`scipy.optimize`模块提供了许多用于优化问题的函数和算法。这些算法可以用于找到函数的最小值、最大值、零点等。
`scipy.optimize`模块提供了许多用于优化问题的函数和算法。这些算法可以用于找到函数的最小值、最大值、零点等。
|
Python
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
351 0
|
存储 算法 索引
1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题
1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题
534 0

热门文章

最新文章