区间子数组个数 图解题解

这道题到底在问什么

输入

nums=[2,1,4,3], left=2, right=3

输出

3　（[2]、[2,1]、[3]）

输入

nums=[2,9,2,5,6], left=2, right=8

输出

7

最优解：一步一步想明白

1. 3记住这套「在界内算距离、偏小延续、超界清零」，下面每一帧都在套它。
2. 4start 记最近一个超过 right 的下标，开局当作 −1（还没出现过墙）。dp 记「以当前元素结尾的合法子数组数」，ans 是累计答案。从第 0 个开始扫。
3. 5第 0 个是 2，2 ≤ 2 ≤ 3，正好落在界内。它自己就能当一段子数组的最大值。
4. 6从 start 右边（下标 0）一直到 0，每个起点配上 0 都是一个合法子数组，共 1 个。绿色高亮的就是这 1 个子数组的起点范围。
5. 7把 dp = 1 累进答案，ans 现在是 1。
6. 8第 1 个是 1，1 < left=2，比下界还小。它当不了最大值，但也不会把最大值顶出界。
7. 91 偏小，把它接到之前那些合法子数组后面，最大值还在原来那个界内元素手里，数量不变，dp 仍是 1。
8. 10把 dp = 1 累进答案，ans 现在是 2。
9. 11第 2 个是 4，4 > right=3，太大了。任何包含它的子数组，最大值都会超过 right。
10. 124 超界，像一堵墙把窗口斩断。以它结尾的合法子数组一个都没有，dp 清零；start 记到 2，之后的窗口只能从墙右边算起。
11. 13这一步给答案加 0，ans 仍是 2。继续往后看。
12. 14第 3 个是 3，2 ≤ 3 ≤ 3，正好落在界内。它自己就能当一段子数组的最大值。
13. 15从 start 右边（下标 3）一直到 3，每个起点配上 3 都是一个合法子数组，共 1 个。绿色高亮的就是这 1 个子数组的起点范围。
14. 16把 dp = 1 累进答案，ans 现在是 3。
15. 17第 4 个是 2，2 ≤ 2 ≤ 3，正好落在界内。它自己就能当一段子数组的最大值。
16. 18从 start 右边（下标 3）一直到 4，每个起点配上 4 都是一个合法子数组，共 2 个。绿色高亮的就是这 2 个子数组的起点范围。
17. 19把 dp = 2 累进答案，ans 现在是 5。
18. 20第 5 个是 5，5 > right=3，太大了。任何包含它的子数组，最大值都会超过 right。
19. 215 超界，像一堵墙把窗口斩断。以它结尾的合法子数组一个都没有，dp 清零；start 记到 5，之后的窗口只能从墙右边算起。
20. 22这一步给答案加 0，ans 仍是 5。继续往后看。
21. 23第 6 个是 3，2 ≤ 3 ≤ 3，正好落在界内。它自己就能当一段子数组的最大值。
22. 24从 start 右边（下标 6）一直到 6，每个起点配上 6 都是一个合法子数组，共 1 个。绿色高亮的就是这 1 个子数组的起点范围。
23. 25把 dp = 1 累进答案，ans 现在是 6。
24. 26全程扫完，每一步以当前元素结尾的合法子数组数依次是 1、1、0、1、2、0、1，相加得 6。这就是最终答案 6，整趟只扫了一遍。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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)

#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);
    }
};

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;
    }
}

复杂度

面试官可能追问