最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

数组篇10_区间子数组个数[难度:中等]

XAMPP相关 admin 273浏览 0评论

来源:LeetCode

难度:中等

描述:

给定一个元素都是正整数的数组A ,正整数 L 以及 R (L <= R)。求连续、非空且其中最大元素满足大于等于L 小于等于R的子数组个数。

示例1:

drf00038

分析:题目要求找出数组中L和R两个整数之间的子数组,注意题目中要求连续,非空,最大元素大于等于L且小于等于R,意味着咱们不能打乱原数组元素之间的顺序,并且每个子数组不能存在大于R的元素,但是可以存在小于L的元素(小于L的元素需和L和R之间的元素一起存在),例如数组 【1, 2, 3】,如果L等于1, R等于2,那么子数组为【1】,【1,2】,【2】,不能出现【2,1】这个组合

题外话:因为该题要求连续性,所以咱们不能直接通过数学公式来求所有子数组组合方式来解了

 

解题

方法一:动态规划法解题

思路:咱们采用一个数组来存储每个位置对应的个数,用dp[i]来表示第i个位置对应的子数组个数,每个位置对应的数组个数有以下几种情况:

 

原数组用A代表:

1、A【i】 大于R,子数组中不能存在大于R的元素,即该位置元素不能参与计算,所以dp【i】= 0

2、A【i】 在L和R之间,该元素为必须参与计算的元素,则该位置参与的计数的子数组个数=该位置下标 – 上一个大于R的元素下标

举个例子:

数列 5,4,3,6,L为3,R为4

那么dp【0】= 0

dp【1】= 该位置下标 – 上一个大于R的元素下标  = 1 – 0 = 1

dp【2】=该位置下标 – 上一个大于R的元素下标  = 2 – 0 = 2

这里解释一下:dp【2】代表下标为2的元素参与计数的个数,分别有 4,3 和3 两个,起始为上一个大于R的元素下标 ,终点为本元素下标,要求连续,所以该元素参与计数的个数即为:下标 – 上一个大于R的元素下标

dp【3】= 0

3、A【i】 小于L,该元素可以参与计算,但必须和在L和R之间一起,如果其上一个元素大于R,那么该元素没有同伴带它进行计算,此时dp【i】= 0,如果上一个元素小于R,那么该位置能形成的个数就等于 上一个元素的(它就负责卖萌混口饭吃),即dp【i】= dp【i – 1】

代码:

 1public static int numSubarrayBoundedMax(int[] nums, int left, int right) {
 2    if (nums == null || nums.length == 0) {
 3        return 0;
 4    }
 5    //dp数组记录每个位置元素对应个数
 6    int[] dp = new int[nums.length];
 7    //记录上一个大于R的位置
 8    int preBreak = -1;
 9    for (int i = 0; i < nums.length; i++) {
10        if (nums[i] > right) {
11            dp[i] = 0;
12            preBreak = i;
13        } else if (nums[i] < left) {
14            dp[i] = dp[i - 1];
15        } else {
16            dp[i] = i - preBreak;
17        }
18    }
19    int res = 0;
20    //结果为每个元素之和
21    for (int value : dp) {
22        res += value;
23    }
24    return res;
25}

时间复杂度:O(n)

空间复杂度:O(n)

 

上面通过数组存储中间结果,咱们也可以用一个数来累加中间结果,直接输出

优化代码:

 1public static int numSubarrayBoundedMax(int[] nums, int left, int right) {
 2    if (nums == null || nums.length == 0) {
 3        return 0;
 4    }
 5    //dp数组记录每个位置元素对应个数
 6    int res = 0;
 7    //记录上一个大于R的位置
 8    int preBreak = -1;
 9    //记录上次 位于l和r之间的个数
10    int lastCount = 0;
11    for (int i = 0; i < nums.length; i++) {
12        if (nums[i] > right) {
13            preBreak = i;
14            lastCount = 0;
15        } else if (nums[i] < left) {
16            //和上次的位于l和r之间的个数一致
17            res += lastCount;
18        } else {
19            //更新
20            lastCount = i - preBreak;
21            res += lastCount;
22        }
23    }
24
25    return res;
26}

时间复杂度:O(n)

空间复杂度:O(1)

 

方法一:计数相减法

思路:题目要求咱们返回l和r之间的子数组个数,咱们可以利用分解法,先分别计算 小于r的子数组个数和小于l的子数组个数,那么两者相减就是结果

num(l<=x<=r) = num(x<r) – num(x<l);

计算小于l的个数和方法一中的思路一致,并且不用考虑第三种情况(只有大于和小于两种情况),咱直接看代码吧

 

代码:

 1public int numSubarrayBoundedMax(int[] nums, int left, int right) {
 2    if (nums == null || nums.length == 0) {
 3        return 0;
 4    }
 5    //right个数 - left 个数,此处left需要减一,因为left元素已经被right包含在内了
 6    return count(nums, right) - count(nums, left - 1);
 7}
 8
 9public static int count(int[] nums, int num) {
10    if (nums == null || nums.length == 0) {
11        return 0;
12    }
13    int res = 0;
14    //记录上一个大于R的位置
15    int preBreak = -1;
16    for (int i = 0; i < nums.length; i++) {
17        if (nums[i] > num) {
18            preBreak = i;
19        } else if (nums[i] <= num) {
20            //res直接累加即可
21            res += i - preBreak;
22        }
23    }
24    return res;
25}

时间复杂度:O(n)

空间复杂度:O(1)

 

以上仅是个人思路解法

转载请注明:XAMPP中文组官网 » 数组篇10_区间子数组个数[难度:中等]

您必须 登录 才能发表评论!