3468. 可行数组的数目

题目描述

给你一个长度为 n 的数组 original 和一个长度为 n x 2 的二维数组 bounds，其中 bounds[i] = [ui, vi]。

你需要找到长度为 n 且满足以下条件的 可能的 数组 copy 的数量：

1. 对于 1 <= i <= n - 1 ，都有 (copy[i] - copy[i - 1]) == (original[i] - original[i - 1]) 。
2. 对于 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 <= 105
• 1 <= original[i] <= 109
• bounds.length == n
• bounds[i].length == 2
• 1 <= bounds[i][0] <= bounds[i][1] <= 109

解法

方法一

Python3JavaC++Go

评论