区间子数组个数

[编程题]区间子数组个数

热度指数：492 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为 n 的整数数组 nums 和两个正整数 l 和 r ，找出 nums 中连续、非空且其中最大元素在范围 [left,right] 内的子数组数目。

数据范围： $1 \le n \le 10^5 \$ ， $0 \le l,r,nums_i \le 10^9 \$

示例1

输入

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

输出

示例2

输入

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

输出

说明

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

算法知识视频讲解

Tieeaa

对于当前值i分为三种情况：

1.nums[i]>right，此时任何包含nums[i]的子数组均不合法，种数为0

2.left<=nums[i]<=right，此时i左侧，第一个大于right的数nums[great_pos]中包含nums[i]的连续子数组均合法，种数为i-great_pos

3.nums[i]<left，此时i左侧第一个大于right的数nums[great_pos]到i左侧第一个值在[left,right]之间的数nums[left_pos]的组合均合法，种数为left_pos-great_pos

以[2,1,4,6,3],2,4为例

2，位于2，4之间，左侧第一个大于4的位置为-1，种数为0-（-1）=1

1：左侧第一个位于2，4之间的数为2，位置为0，种数为1-0=1

4：位于2，4之间，左侧第一个大于4的位置为-1，种数为2-（-1）=4

6：大于4，种数为0

3：位于2，4之间，左侧第一个大于4的位置为3，种数为4--3=1

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param l int整型 
     * @param r int整型 
     * @return int整型
     */
    int countSubarray(vector<int>& nums, int l, int r) {
        // write code here
        int great_pos = -1;
        int left_pos = -1;
        int res = 0;
        for(int i=0;i<nums.size();++i){
            if(nums[i]>=l&&nums[i]<=r){
                left_pos = i;
                res+=left_pos-great_pos;
            }else if(nums[i]<l){
                res+=left_pos-great_pos;
            }else{
                great_pos = i;
                left_pos = i;
            }
        }
        return res;
    }
};

发表于 2023-08-09 09:36:49 回复(0)

Python2

菜鸡升职记

# -*- coding: utf-8 -*-

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @param l int整型
# @param r int整型
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/46a66d7a88574983beb59ac2f20b5019?tpId=196&tqId=40557&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    参考：
        大神：夏花灿烂秋叶静美
    算法：
        题目要求：统计子区间的最大值在[l, r]之间的区间个数
        我们对问题进行转化：我们可以统计出最大值小于等于r的子区间个数rNum，以及最大值小于l的子区间个数lNum，两者之差就是所求结果rNum - lNum。
        使用lStart和rStart分别记录当前满足 小于等于r 和 小于l的区间起点，当nums[i] <= r时，统计不重复的满足条件的子区间个数，否则，重置rStart = i + 1；当nums[i] < l时，统计不重复的满足条件的子区间个数，否则，重置lStart = i + 1。
    复杂度：
        时间复杂度：O(n)
        空间复杂度：O(1)
    """

    def countSubarray(self, nums, l, r):
        # write code here
        n, lStart, rStart, lNum, rNum = len(nums), 0, 0, 0, 0

        for i in range(n):
            if nums[i] <= r:
                rNum += i - rStart + 1
            else:
                rStart = i + 1

            if nums[i] < l:
                lNum += i - lStart + 1
            else:
                lStart = i + 1

        return rNum - lNum

if __name__ == "__main__":
    sol = Solution()

    # nums, l, r = [2, 1, 4, 6, 3], 2, 4

    nums, l, r = [2, 1, 4, 3], 2, 3

    res = sol.countSubarray(nums, l, r)

    print res

发表于 2022-07-08 10:45:22 回复(0)

Java

牛客271979301号

动态规划

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)