Daily LeetCode 795. Number of Subarrays with Bounded Maximum

https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/

Medium

问题分析：

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]，要求求出连续非空子串的个数，这个子串的最大值在区间[L, R]内。

思路: 动态规划

维护一个一维的状态数组dp，dp[i]表示以A[i]结尾的数组中，符合条件的子串的个数；设置一个子串开始标志sub_start。

状态转移方程有下列几种情况：

1. 当A[index] > R时：
   由于当前元素超出了范围，因此加上这个元素后，子串不符合条件，此时dp[index]=0，同时，将sub_start设置为当前位置的index。
2. 当A[index] < L时：
   当前元素小于范围，这个元素对子串数量没有影响，此时dp[index]=dp[index-1]
3. 当L<=A[index]<=R时：
   当前元素处于范围内，由于要求构造连续的子串，我们只需要考虑从sub_start到index这个范围内的连续子串，这个范围内的连续子串个数为index-sub_start，因此，dp[index] = index - sub_start

代码：

class Solution:
    def numSubarrayBoundedMax(self, A: List[int], L: int, R: int) -> int:
        dp = [0 for _ in range(len(A))]
        sub_start = -1

        for index, num in enumerate(A):
            if num < L:
                dp[index] = dp[index - 1]
            elif num > R:
                dp[index] = 0
                sub_start = index
            else:
                dp[index] = index - sub_start

        return sum(dp)