Daily LeetCode – day0118 0795. Number of Subarrays with Bounded Maximum

// 0795. Number of Subarrays with Bounded Maximum
class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        int ans = 0;
        int lastBigger = -1;
        int lastIn = -1;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] > right) {
                lastBigger = i;
                lastIn = -1;
            } else if (nums[i] >= left) {
                lastIn = i;
            }
            if (lastIn != -1) {
                ans += lastIn - lastBigger;
            }
        }
        return ans;
    }
}
学习笔记:
这是一道非常巧妙的数组题目。
我们要把数字分成三类,比范围大的,在范围内的,比范围小的。也可以理解为210三种。
然后记录上一次出现比范围大的数字的索引,还有上一次出现范围内的数字的索引。
这样只从左往右遍历一次就可以算出结果。
每一个位子往左看,能符合条件的其实就是上一次出现范围内的(包括自己先在位子)减去上一次出现大于范围的。
20101
那2就不用加,
到0也没得加,
到1可以加2,
到0还是可以加2,
到1可以加4。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注