lc795 区间子数组个数

给定数组nums[n]和两个整数left,right，找出nums中连续非空、并且最大元素在[left,right]范围内的子数组，统计所有满足条件子数组的个数。
1<=n<=1e5; 0<=nums[i]<=1e9; 0<=left<=right<=1e9; 保证答案在int内

枚举每个元素作为最大元素的情况，统计对应的子数组数量，如果arr[i]在允许范围内，则对答案有贡献。

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
        int n = nums.size();
        vector<int> L(n), R(n), s;
        for (int i = 0; i < n; i++) {
            while (!s.empty() && nums[i] > nums[s.back()])
                s.pop_back();
            L[i] = s.empty() ? -1 : s.back();
            s.push_back(i);
        }
        s.clear();
        for (int i = n-1; i >= 0; i--) {
            while (!s.empty() && nums[i] >= nums[s.back()])
                s.pop_back();
            R[i] = s.empty() ? n : s.back();
            s.push_back(i);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) if (left <= nums[i] && nums[i] <= right) {
            ans += (i-L[i]) * (R[i]-i);
        }
        return ans;
    }
};