leetcode刷题笔记:number-of-subarrays-with-bounded-maximum（ 动态规划 && 单
题目地址:
https://leetcode.cn/problems/number-of-subarrays-with-bounded-maximum/
题目描述
Given an integer array nums and two integers left and right, return the number of contiguous non-empty subarrays such that the value of the maximum array element in that subarray is in the range [left, right].
The test cases are generated so that the answer will fit in a 32-bit integer.
Example 1:
Input: nums = [2,1,4,3], left = 2, right = 3
Output: 3
Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].
Example 2:
Input: nums = [2,9,2,5,6], left = 2, right = 8
Output: 7
题目大概就是要求一个数组的子数组中最大值满足在范围[left, right]的个数。
虽然难度为中等， 但是这题有很多种方法解决，于是写篇博客随便复习一下。
思路1: 动态规划
我们先来证明这个问题是具有子结构的，也就是说我们可以从解决子问题开始最终能得出我们的答案。
我们先来定义子问题，要求数组最终的子数组满足的个数, 我们可以定义 i 表示以 i 作为最后元素中子数组的个数, 于是我们就拆解出了 i 个子问题, 假设这 i 个子问题的解为
那么根据题意问题的答案为 , 即每个以 i 结尾的子数组的个数的和。由子数组的性质可知，每个子问题
都是唯一的， 递归地,
也是唯一的，于是我们证明了可以从子问题中推出原问题的解，这个问题是具有子结构的。
一个问题证明了具有子结构后，我们就可以通过递归或递推(动态规划)来解决了，我们先假设出状态:
dp[i][0] : 以 i 作为最后元素中子数组的最大值小于在 [left, right] 中的个数
dp[i][1] : 以 i 作为最后元素中子数组的最大值在 [left, right] 中的个数
已知 nums 里面的元素会出现三种情况:
当 nums[i] >= left 且 nums <= right : 此时 nums[i] 一定会出现在符合的子数组中, 由于符合的子数组中满足 nums[i] 为最大值即可, 那么还可能出现比 nums[i] 小的元素, 并且要求是连续的，所有该子问题的解可以转化为 i - 1 (上一个)状态的解:
我们此时的状态方程可以这样写:
dp[i][1] = 1 + dp[i - 1][1] + dp[i - 1][0]
当 nums[i] < left : dp[i][0] = dp[i - 1][0] + 1
dp[i][1] = dp[i - 1][1]
当 nums[i] > right 时: 这个元素对我们的答案没有如何贡献, 此时dp[i][0] = dp[i][1] = 0
注意到每个状态只与上一个状态有关，我们还可以用滑动数组进行优化(这里就不写惹。。。)
思路2: 单调栈
对于数组里面的每一个元素 nums[i], 我们考虑它对答案的贡献。如果这个 nums[i] 在 [left, right] 范围内， 我们定义 l[i] 为 nums[i] 左边第一个大于 nums[i] 的元素的下标, r[i] 为 nums[i] 右边第一个大于 nums[i] 的元素的下标, 那么已nums[i]为最大值的子数组有 (i - l[i]) * (r[i] - i) 个(相当于组合问题吧。。。)， 那么我们对每个 (i - l[i]) * (r[i] - i) 求和就是答案了。
其中 l[i] 和 r[i] 可以通过 单调栈 这种数据结构来计算出来。时间复杂度仅为 O(n)。
思路3: 模拟 + 计数
利用前缀和的思想，我们先计算出 x = 最大值为 right 的子数组的个数, y = 最大值为 left - 1 的子数组的个数, 然后 x - y 就是 最大值范围在 [left, right]的子数组的个数了!
