2145-统计隐藏数组数目

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

给你一个下标从 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 <= 105
  • -105 <= differences[i] <= 105
  • -105 <= lower <= upper <= 105

方法一：确定隐藏数组上下界的差值

思路与算法

记最终的数组为 a_0, a_1, \cdots, a_n。我们可以发现，如果数组 a 满足要求，那么：

a_0 + k, a_1 + k, \cdots, a_n + k

也一定满足要求。这里的「要求」指的是相邻元素的差值对应着给定的数组 differences。

因此我们就可以任意指定 a_0，为了方便不妨直接令 a_0 = 0，我们就可以还原出数组 a_0, a_1, \cdots, a_n 了。如果我们继续考虑数组元素都在 [\textit{lower}, \textit{upper}] 范围内的要求，不妨记数组中最小的元素为 a_i，最大的元素为 a_j，显然需要满足：

\textit{lower} \leq a_i \leq a_j \leq \textit{upper}

那么 a_i 的取值下界即为 lower，上界为 upper} - (a_j - a_i)，即需要保证最大值 a_j 不能超过 upper。这里的 a_j - a_i 实际上与 a_i, a_j 本身的值无关，它就等于：

\sum_{k=i}^{j-1} \textit{differences}[k]

因此符合要求的隐藏数组的数目即为 upper} - (a_j - a_i) - \textit{lower} + 1，整理可得：

(\textit{upper} - \textit{lower}) - (a_j - a_i) + 1

实际上就是规定的数组元素的区间长度，减去数组元素最大值与最小值的差值，再加上 1。我们可以将其看成是一个长度为 a_j - a_i 的小窗口在长度为 upper} - \textit{lower 的大窗口中滑动时，能够放置的位置数量。

细节

在还原数组 a 的过程中，我们无需记录整个数组，而是只需要记录最大值和最小值即可。如果某一时刻最大值与最小值的差值大于 upper} - \textit{lower，我们可以直接返回 0。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int numberOfArrays(vector<int>& differences, int lower, int upper) {
        int x = 0, y = 0, cur = 0;
        for (int d: differences) {
            cur += d;
            x = min(x, cur);
            y = max(y, cur);
            if (y - x > upper - lower) {
                return 0;
            }
        }
        return (upper - lower) - (y - x) + 1;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
        x = y = cur = 0
        for d in differences:
            cur += d
            x = min(x, cur)
            y = max(y, cur)
            if y - x > upper - lower:
                return 0
        return (upper - lower) - (y - x) + 1
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func numberOfArrays(differences []int, lower int, upper int) int {
	var x, y, cur int
	for _, d := range differences {
		cur += d
		x, y = min(x, cur), max(y, cur)
		if y-x > upper-lower {
			return 0
		}
	}
	return (upper - lower) - (y - x) + 1
}

func min(x, y int) int {
	if x > y {
		return y
	}
	return x
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

复杂度分析

  • 时间复杂度：O(n)。

  • 空间复杂度：O(1)。

 Comments
On this page
2145-统计隐藏数组数目