登陆

算法日志 --- 11.24---区间子数组个数

admin 2022-11-24 14人围观 ,发现0个评论

开启掘金成长之旅!这是我参与「掘金日新计划 · 12 月更文挑战」的第4天,点击查看活动详情

真正的疯狂星期四,但是疫情席卷而来,又要禁堂食了

区间子数组个数

该题出自力扣的795题 —— 区间子数组个数【中等题】

审题

给你一个整数数组 nums 和两个整数:left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组,并返回满足条件的子数组的个数。 生成的测试用例保证结果符合 32-bit 整数范围。

image.png

  • 这道题的题意并不复杂,虽然是中等题,但是很好理解,因为,题目给出三个参数
    • 一个整型数组,两个整数变量
    • 两个整数变量形成一个区间
    • 最终返回在这个区间内的子数组个数
  • 最初的想法就是利用暴力遍历解法,但是需要留意每一次新元素可以对前面的子数组进行全部加一,而且因为用例在10的9次方,所以预估会超时,没有进行尝试
  • 利用计数法,L到R的最大个数等于R的最大子数组减去L的最大子数组,举个例子就是:L为3,R为5,求L到R的距离,那么就可以利用0到R的距离减去0到L的距离,那就是用R减去L即可
    • 利用一个自定义函数,计算出数组内,小于变量的最大子数组个数
    • 用R的函数结果减去L的函数结果
  • 这样会进行两次完整的遍历,虽然复杂度还是O(n),但不不可避免的还是会性能损耗,那么可以利用一次遍历去解决

编码

class Solution {     public int numSubarrayBoundedMax(int[] nums, int left, int right) {         return help(nums,right) - help(nums,left - 1);     }      private int help(int[] nums, int left) {         int max = 0;         int index = 0;         for(int num : nums){             if (num<= left){                 index++;                 max += index;             }else {                 index = 0;             }         }         return max;     } } 复制代码

image.png

请发表您的评论
请关注微信公众号
微信二维码
不容错过
Powered By Z-BlogPHP