795.区间子数组个数

链接：795.区间子数组个数
难度：Medium
标签：数组、双指针
简介：给你一个整数数组 nums 和两个整数：left 及 right 。找出 nums 中连续、非空且其中最大元素在范围  [left, right] 内的子数组，并返回满足条件的子数组的个数。

题解 1 - cpp

• 编辑时间：2022-11-24
• 执行用时：108ms
• 内存消耗：56.3MB
• 编程语言：cpp
• 解法介绍：单调栈求出每个点最近比他大的左值和右值，判断当前点是最大值的情况。

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
        int n = nums.size(), ans = 0;
        vector<int> llist(n, -1), rlist(n, n);
        stack<int> s;
        for (int i = 0; i < n; i++) {
            while (s.size() && nums[s.top()] <= nums[i]) {
                rlist[s.top()] = i;
                s.pop();
            }
            llist[i] = s.empty() ? -1 : s.top();
            s.push(i);
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] > right || nums[i] < left) continue;
            int left = i - llist[i] - 1, right = rlist[i] - i;
            ans += left + right + (left * (right - 1));
        }
        return ans;
    }
};

题解 2 - cpp

• 编辑时间：2022-11-24
• 执行用时：48ms
• 内存消耗：51.1MB
• 编程语言：cpp
• 解法介绍：一次遍历，统计出不包含>right 的值且最少包含一个>=left 的值的个数。

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
        int n = nums.size(), ans = 0, prev = -1, cur = -1;
        for (int i = 0; i < n; i++) {
            if (nums[i] <= right && nums[i] >= left) cur = i;
            else if (nums[i] > right) prev = i, cur = -1;
            if (cur != -1) ans += cur - prev;
        }
        return ans;
    }
};