题目描述：

LeetCode 795. Number of Subarrays with Bounded Maximum

We are given an array A of positive integers, and two positive integers L and R (L <= R).

Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least L and at most R.

Example :
Input: 
A = [2, 1, 4, 3]
L = 2
R = 3
Output: 3
Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].

Note:

• L, R  and A[i] will be an integer in the range [0, 10^9].
• The length of A will be in the range of [1, 50000].

题目大意：

给定只含有正整数的数组A，两个正整数L和R。

求A中最大值在[L, R]之间的连续子序列个数。

解题思路：

组合（Combination）

在A中找出所有大于R的整数，将这些整数消去，并将A分为若干个子数组

对于上一步得到的任意数组a，从左向右找出所有不小于L的整数

假设某个这样的整数为x，下标为i；记该整数左侧相邻的不小于L的整数y的下标为j

则所有包含整数x的连续子序列个数为：(i - j) * (len(A) - i)

Python代码：

class Solution(object):
    def numSubarrayBoundedMax(self, A, L, R):
        """
        :type A: List[int]
        :type L: int
        :type R: int
        :rtype: int
        """
        ans = lastIdx = 0
        for i, x in enumerate(A + [10**10]):
            if x > R:
                ans += self.numSubarrayMinimumMax(A[lastIdx:i], L)
                lastIdx = i + 1
        return ans

    def numSubarrayMinimumMax(self, A, L):
        """
        :type A: List[int]
        :type L: int
        :rtype: int
        """
        ans = lastIdx = 0
        for i, x in enumerate(A):
            if x >= L:
                ans += (i - lastIdx + 1) * (len(A) - i)
                lastIdx = i + 1
        return ans

 

本文链接：http://bookshadow.com/weblog/2018/03/04/leetcode-number-of-subarrays-with-bounded-maximum/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码