首页 > 试题广场 >

区间子数组个数

[编程题]区间子数组个数
  • 热度指数:497 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个长度为 n 的整数数组 nums 和两个正整数 l 和 r ,找出 nums 中连续、非空且其中最大元素在范围 [left,right] 内的子数组数目。

数据范围:
示例1

输入

[2,1,4,6,3],2,4

输出

6
示例2

输入

[2,1,4,3],2,3

输出

3

说明

[2] , [2,1] , [3] 
动态规划
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param nums int整型ArrayList
     * @param l int整型
     * @param r int整型
     * @return int整型
     */

    public int countSubarray (ArrayList<Integer> nums, int l, int r) {
        // write code here
        int[] dp = new int[nums.size()];
        int temp = 0;
        int big = 0;
        int small = 0;
        boolean fix=false;
        int op=0;
        for (int i = 0; i < nums.size(); i++) {
            int c = nums.get(i);
            if (c >= l && c <= r) {
                fix=true;
                temp = i + 1 - big;
                dp[i] = dp[i > 0 ? i - 1 : 0] + temp;
                op=i;
            } else if (c < l) {
                if(!fix){
                    dp[i]=dp[i>0?i-1:0];
                }
                else {
                    small =op+1-big;
                    dp[i] = dp[i > 0 ? i - 1 : 0] + small;
                }
            } else {
                fix=false;
                dp[i] = dp[i > 0 ? i - 1 : 0];
                big = i+1;
            }
        }
        return dp[nums.size() - 1];
    }

}
发表于 2022-06-28 21:44:17 回复(0)