题目要求:对所有非空连续子数组,把各自的最大值加总,再对 109+7 取模。
直接枚举所有区间是 O(n2),在 n=105 时不可行。换贡献视角:对每个下标 i,统计有多少个子数组以 loads[i] 为最大值,再累加 loads[i]×次数。
用单调栈求左右跨度:
云平台 SRE 要对某核心集群做巡检风险评估。监控系统按固定周期采样,得到长度为 n 的负载序列 loads(下标从 0 开始,单位自定)。
风控规则这样定义「时段风险」:
现在需要统计:所有可能的巡检时段(即所有非空连续子数组)的风险分之和,作为集群的「累计峰值风险」。由于答案可能很大,请对 109+7 取模后返回。
请实现:
sumPeakRisk(loads: int[]) -> int
思考提示:直接枚举所有区间是 O(n2) 的;需要换一个角度——考虑每个采样点作为「某段区间峰值」时,能向左、向右延伸多远,再累计贡献。
一行:整数数组 loads。
约束:
一个整数:所有非空连续子数组最大值之和,对 109+7 取模。
输入:
[1, 2, 3]
输出:
14
说明:全部子数组及其峰值为
[1]→1,[1,2]→2,[1,2,3]→3,[2]→2,[2,3]→3,[3]→3。
总和 1+2+3+2+3+3=14。
输入:
[3, 1, 2]
输出:
14
说明:[3]→3,[3,1]→3,[3,1,2]→3,[1]→1,[1,2]→2,[2]→2,总和 14。
输入:
[2, 2]
输出:
6
说明:两个单点贡献 2+2,整段 [2,2] 峰值仍为 2,总和 6。
(相等时,需要约定左右边界的归属,避免同一区间被重复或漏计——请在实现中自行处理并列峰值。)
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.