区间子数组个数

# -*- 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