LeetCode每日一题2025-04-21

点击获取AI摘要

2145. 统计隐藏数组数目 M

给你一个下标从 0 开始且长度为 n 的整数数组 differences ，它表示一个长度为 n + 1 的 隐藏 数组 相邻 元素之间的 差值 。更正式的表述为：我们将隐藏数组记作 hidden ，那么 differences[i] = hidden[i + 1] - hidden[i] 。

同时给你两个整数 lower 和 upper ，它们表示隐藏数组中所有数字的值都在 闭 区间 [lower, upper] 之间。

• 比方说，differences = [1, -3, 4] ，lower = 1 ，upper = 6 ，那么隐藏数组是一个长度为4 且所有值都在 1 和 6 （包含两者）之间的数组。
  • [3, 4, 1, 5] 和 [4, 5, 2, 6] 都是符合要求的隐藏数组。
  • [5, 6, 3, 7] 不符合要求，因为它包含大于 6 的元素。
  • [1, 2, 3, 4] 不符合要求，因为相邻元素的差值不符合给定数据。

请你返回 符合 要求的隐藏数组的数目。如果没有符合要求的隐藏数组，请返回 0 。

示例 1：

输入：differences = [1,-3,4], lower = 1, upper = 6
输出：2
解释：符合要求的隐藏数组为：

• [3, 4, 1, 5]
• [4, 5, 2, 6]

所以返回 2 。

示例 2：

输入：differences = [3,-4,5,1,-2], lower = -4, upper = 5
输出：4
解释：符合要求的隐藏数组为：

• [-3, 0, -4, 1, 2, 0]
• [-2, 1, -3, 2, 3, 1]
• [-1, 2, -2, 3, 4, 2]
• [0, 3, -1, 4, 5, 3]

所以返回 4 。

示例 3：

输入：differences = [4,-7,2], lower = 3, upper = 6
输出：0
解释：没有符合要求的隐藏数组，所以返回 0 。

提示：

• n == differences.length
• 1 <= n <= $10^5$
• $-10^5$ <= differences[i] <= $10^5$
• $-10^5$ <= lower <= upper <= $10^5$

问题分析

1. 前缀和（Prefix Sums）

   定义

   $$P_0=0,\quad P_i=\sum_{k=0}^{i-1}\text{differences}[k]\quad(1\leq i\leq n).$$

   则隐藏数组第 $i$ 个元素有

   $$\text{hidden}[i]=\text{hidden}[0]+P_i.$$

2. 区间约束转化

   要保证所有元素都在 $[\text{lower},\;\text{upper}]$ 之间，即对所有 $0\le i\le n$ 都有

   $$\text{lower}\le \text{hidden}[0]+P_i \le \text{upper}.$$

   等价于

   $$\max_{i}\bigl(\mathrm{hidden}[0] + P_{i}\bigr) \leq \mathrm{upper} \quad\Longrightarrow\quad \mathrm{hidden}[0] \leq \mathrm{upper} - \max_{i} P_{i},$$

   $$\min_{i}\bigl(\mathrm{hidden}[0] + P_{i}\bigr) \geq \mathrm{lower} \quad\Longrightarrow\quad \mathrm{hidden}[0] \geq \mathrm{lower} - \min_{i} P_{i}.$$

   $$\mathrm{hidden}[0]\leq\mathrm{upper}-\max_iP_i,\quad\mathrm{hidden}[0]\geq\mathrm{lower}-\min_iP_i.$$

3. 可行起始值个数

   记 $minP=\min_iP_i,maxP=\max_iP_i$ 。

   那么

   $$\mathrm{hidden}[0]∈[\mathrm{lower}−\min\text{P},\mathrm{upper}−\max\text{P}],$$

   区间长度（整数个数）为

   $$(\mathrm{~upper}-maxP)-(\mathrm{~lower}-minP)+1=(\mathrm{upper}-\mathrm{lower})-(maxP-minP)+1.$$

   若该值为负，则答案是0。

算法思路

1. 遍历一次 differences，用变量 curr 累加差分，实时维护 minP = min(minP, curr) 和 maxP = max(maxP, curr)。

2. 根据上面推导，计算可行的 hidden[0] 的左端点 L = lower - minP，右端点 R = upper - maxP。

3. 答案即为 max(0, R - L + 1)。

时间复杂度

• 算法的时间复杂度为$O(n)$，其中$n$是differences数组的长度。因为只需遍历一次差异数组即可计算所有必要的参数，没有嵌套循环，因此效率较高。

• 仅使用常数级额外空间，故空间复杂度为$O(1)$。

代码实现

# 先求前缀极值再统一算区间
class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
        # 初始化前缀和的最小值和最大值
        minP = 0
        maxP = 0
        curr = 0
        
        # 遍历差分数组，更新前缀和区间
        for d in differences:
            curr += d
            minP = min(minP, curr)
            maxP = max(maxP, curr)
        
        # 计算起始值 hidden[0] 的可行区间 [L, R]
        L = lower - minP
        R = upper - maxP
        
        # 区间长度即为符合要求的数组个数
        return max(0, R - L + 1)

也可直接把对每个位置的区间约束（本质相同）

$$\mathrm{lower}\leq\mathrm{hidden}[0]+P_i\leq\mathrm{upper}$$

转化为对 hidden[0] 的上下界，并在遍历中不断收缩，最终得出相同可行区间 $[\max\{\underline{L}\},\min\{\overline{R}\}]$

维护上下界

• 令 curr = P_i，初始 curr = 0。
• 看到新的curr就把 $\mathrm{hidden}[0]\geq\mathrm{lower}-\mathrm{curren}t_s$ 转化为下界 L = lower - curr并往上取最大，把 $\mathrm{hidden}[0]\leq\mathrm{upper}-\mathrm{curren}t_s$ 转化为上界 R = upper - curr并往下取最小。
• 每步累加差分 curr += d 后

若 L > R 则 0，否则 R - L + 1。

# 遍历中直接收敛上下界
from typing import List

class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
        curr = 0
        L = lower      # lower - 0
        R = upper      # upper - 0
        for d in differences:
            curr += d
            candL = lower - curr
            if candL > L:
                L = candL
            candR = upper - curr
            if candR < R:
                R = candR
        return max(0, R - L + 1)