3468. 可行数组的数目
题目描述
给你一个长度为 n 的数组 original 和一个长度为 n x 2 的二维数组 bounds，其中 bounds[i] = [ui, vi]。
你需要找到长度为 n 且满足以下条件的 可能的 数组 copy 的数量：
- 对于
1 <= i <= n - 1，都有(copy[i] - copy[i - 1]) == (original[i] - original[i - 1])。 - 对于
0 <= i <= n - 1，都有ui <= copy[i] <= vi。
返回满足这些条件的数组数目。
示例 1
输入：original = [1,2,3,4], bounds = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：
可能的数组为：
[1, 2, 3, 4][2, 3, 4, 5]
示例 2
输入：original = [1,2,3,4], bounds = [[1,10],[2,9],[3,8],[4,7]]
输出：4
解释：
可能的数组为：
[1, 2, 3, 4][2, 3, 4, 5][3, 4, 5, 6][4, 5, 6, 7]
示例 3
输入：original = [1,2,1,2], bounds = [[1,1],[2,3],[3,3],[2,3]]
输出：0
解释：
没有可行的数组。
提示：
2 <= n == original.length <= 1051 <= original[i] <= 109bounds.length == nbounds[i].length == 21 <= bounds[i][0] <= bounds[i][1] <= 109
解法
方法一
思考
复制数组要落在每维给定区间内，且相邻差与原数组相同。区间个数即数组长度，差值一旦固定，整个数组由首项决定。
设首项为 \(x\)，则第 \(i\) 项为 \(x+\textit{pref}[i]\)，必须落入 \([\textit{bounds}[i][0],\textit{bounds}[i][1]]\)。这给出 \(x\) 的一组不等式。
把各维对 \(x\) 的可行区间求交，交集长度（整数个数）即方案数；空则 \(0\)。
1 | |
1 | |
1 | |
1 | |