leetcode 795. Number of Subarrays with Bounded Maximum 区间子数组个数-耗时100%

Problem: 795. Number of Subarrays with Bounded Maximum 区间子数组个数

解题过程

耗时100%，使用了动态规划的，dp[i]代表以nums[i]结尾的连续子数组数量，一定包含nums[i]

对于>right的数字，其dp[j]一定是0，若left=2, right=3, 对数组 2 3 2，其dp数组是 1 2 3，也就是以2结尾的连续子数组数量是1，以3结尾的连续子数组数量是2（23，3），以2结尾的连续子数组数量是3（232 32 2），所以累加即可

对于 <left的数字，因可以放在其他连续子数组当中，所以dp[i] = count，像 left=2, right=3，对数组 2 3 2 1 1 2，其dp数组是 1 2 3 3 3 6，在【left，right】之间的dp是累加的，所以dp[5] = 6，dp[3] = 3即以1结尾的连续子数组数量和dp[2]相同 dp[4]=dp[3]=dp[2]

left=2, right=3

像 2 1 1 2 3 1 1 2 3
对应的动态规划数组是： 1 1 1 4 5 5 5 8 9

最后将dp累加起来的，就是最后的答案

Code

class Solution { public: int numSubarrayBoundedMax(vector<int>& nums, int left, int right) { int n = nums.size(), cnt=0, count = 0; vector<int> dp(n, 0); for(int i = 0; i < nums.size(); i++) { if(nums[i] > right) { cnt = 0; count = 0; dp[i] = 0; } else if(nums[i] >= left && nums[i] <= right) { count++; dp[i] = count; cnt = count; } else if(nums[i] < left) { count++; dp[i] = cnt; } } int sum = 0; for(int i = 0; i < n; i++) { sum += dp[i]; } return sum; } };