区间子数组个数 图解题解

所谓「最大值落在界内」的子数组，怎么数出来

给数组 nums 和两个界 left、right，要数出有多少个连续非空子数组，它的最大元素既 ≥left 又 ≤right，即最大值落在闭区间 [left, right]（含两端）里。题面 nums=[2,1,4,3]、left=2、right=3 时答案是 3：[2] 最大值 2、[2,1] 最大值 2、[3] 最大值 3 都卡在界内；含 4 的子数组最大值超界，单独一个 1 的又不够，都不算。

把每个子数组都框出来求最大值，慢在哪

顺着定义枚举每个子数组：固定左端，右端一路往后扩，扩时记住当前最大值，看它落不落在 [left, right]。子数组共 O(n²) 个，逐个查是 O(n²) 时间。n 上万时平方级就吃力，得想个一遍扫完的办法。

数「恰在界内」难，数「不超某条线」却容易

直接数「最大值恰好在 [left, right]」两头都卡着，不好下手。换个角度：定义 f(x)= 最大值 ≤x 的子数组个数，只卡上界，而「所有元素都 ≤x」的子数组好数得多。最大值 ≤right 的子数组共 f(right) 个，其中最大值还 ＜left（即 ≤left−1）的那批共 f(left−1) 个，是前者的子集。拿 f(right) 减掉 f(left−1)，剩的就是最大值 ≤right 又 ≥left 的，落在 [left, right] 的那些。答案 = f(right) − f(left−1)。

只卡一个上界，f(x) 一遍扫描就数得出

f(x) 能一遍线性扫出来。扫数组时维护一个 t，表示「以当前元素结尾、且这一段没有元素超过 x 的子数组个数」。碰到 v ≤x，它接在合法段后、也能自己单独成段，t 加一——以它结尾，每往右延一个合法元素就多一个左端点，加一而非翻倍；碰到 v ＞x，它像一堵墙，以它结尾的合法段一个没有，t 归零。每步把 t 累进 cnt，扫完就是 f(x)。一次遍历、几个计数器。

[2,1,4,3] 上，f(3) 与 f(1) 分别怎么算

right=3，先算 f(3)。v=2 ≤3，t=1，cnt=1；v=1 ≤3，t=2，cnt=3；v=4 ＞3，t 归零，cnt 仍是 3；v=3 ≤3，t=1，cnt=4。得 f(3)=4。再算 f(left−1)=f(1)。v=2 ＞1，t=0，cnt=0；v=1 ≤1，t=1，cnt=1；v=4 ＞1，t=0，cnt=1；v=3 ＞1，t=0，cnt=1。得 f(1)=1。答案 f(3) − f(1) = 4 − 1 = 3。

差分下界写成 f(left)，等于 left 的那些就被误删

两次 f(x) 各扫一遍，合起来仍是 O(n) 时间、O(1) 空间。两处容易写坏：一是差分下界得是 f(left−1) 不是 f(left)，写成 f(left) 会把最大值恰好等于 left 的合法子数组也一并扣掉，答案偏小；二是墙必须清零，v ＞x 时忘了把 t 归零、让它继续加，跨过墙、含超界元素的子数组就被错数进来。边界上，全部元素超界或全部 ＜left 时，f(right) 与 f(left−1) 相减都是 0，只有出现界内元素才数得出来。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
        def f(x):
            cnt = t = 0
            for v in nums:
                t = 0 if v > x else t + 1
                cnt += t
            return cnt

        return f(right) - f(left - 1)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
        auto f = [&](int x) {
            int cnt = 0, t = 0;
            for (int& v : nums) {
                t = v > x ? 0 : t + 1;
                cnt += t;
            }
            return cnt;
        };
        return f(right) - f(left - 1);
    }
};

Java

import java.util.*;
class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        return f(nums, right) - f(nums, left - 1);
    }

    private int f(int[] nums, int x) {
        int cnt = 0, t = 0;
        for (int v : nums) {
            t = v > x ? 0 : t + 1;
            cnt += t;
        }
        return cnt;
    }
}