给定一个长度为 n 的整数数组 nums 和两个正整数 l 和 r ,找出 nums 中连续、非空且其中最大元素在范围 [left,right] 内的子数组数目。
数据范围: ,
# -*- 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