Medium

题目描述

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

你需要找到长度为 n 的可能数组 copy 的数量，使得：

  • (copy[i] - copy[i - 1]) == (original[i] - original[i - 1]) 对于 1 <= i <= n - 1
  • ui <= copy[i] <= vi 对于 0 <= i <= n - 1

返回这样的数组数量。

示例 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 <= 10^5
  • 1 <= original[i] <= 10^9
  • bounds.length == n
  • bounds[i].length == 2
  • 1 <= bounds[i][0] <= bounds[i][1] <= 10^9

解题思路

这道题的核心思想是理解题目约束条件的含义。由于 copy 数组与 original 数组相邻元素的差值必须相同，这意味着一旦确定了 copy[0] 的值，整个 copy 数组就完全确定了。

具体来说，如果 copy[0] = x，那么：

  • copy[1] = x + (original[1] - original[0])
  • copy[2] = x + (original[2] - original[0])
  • …
  • copy[i] = x + (original[i] - original[0])

因此，我们需要找到有多少个 x 值使得对于所有的 i，都有 bounds[i][0] <= copy[i] <= bounds[i][1]。

算法步骤：

  1. 首先确定 copy[0] 的初始范围：[bounds[0][0], bounds[0][1]]
  2. 对于每个后续位置 i，计算如果 copy[0] = x，那么 copy[i] 的值
  3. 根据 bounds[i] 的约束，反推出 copy[0] 的有效范围
  4. 取所有约束的交集，得到最终的有效范围
  5. 返回有效范围的大小

关键是要处理整数溢出和边界情况，确保计算过程中的数值在合理范围内。

代码实现

class Solution {
public:
    int countArrays(vector<int>& original, vector<vector<int>>& bounds) {
        long long minVal = bounds[0][0];
        long long maxVal = bounds[0][1];
        
        int n = original.size();
        
        for (int i = 1; i < n; i++) {
            long long diff = (long long)original[i] - original[0];
            
            // copy[i] = copy[0] + diff
            // bounds[i][0] <= copy[0] + diff <= bounds[i][1]
            // bounds[i][0] - diff <= copy[0] <= bounds[i][1] - diff
            
            long long newMin = (long long)bounds[i][0] - diff;
            long long newMax = (long long)bounds[i][1] - diff;
            
            minVal = max(minVal, newMin);
            maxVal = min(maxVal, newMax);
            
            if (minVal > maxVal) {
                return 0;
            }
        }
        
        return (int)(maxVal - minVal + 1);
    }
};

class Solution:
    def countArrays(self, original: List[int], bounds: List[List[int]]) -> int:
        min_val = bounds[0][0]
        max_val = bounds[0][1]
        
        n = len(original)
        
        for i in range(1, n):
            diff = original[i] - original[0]
            
            # copy[i] = copy[0] + diff
            # bounds[i][0] <= copy[0] + diff <= bounds[i][1]
            # bounds[i][0] - diff <= copy[0] <= bounds[i][1] - diff
            
            new_min = bounds[i][0] - diff
            new_max = bounds[i][1] - diff
            
            min_val = max(min_val, new_min)
            max_val = min(max_val, new_max)
            
            if min_val > max_val:
                return 0
        
        return max_val - min_val + 1

public class Solution {
    public int CountArrays(int[] original, int[][] bounds) {
        long minVal = bounds[0][0];
        long maxVal = bounds[0][1];
        
        int n = original.Length;
        
        for (int i = 1; i < n; i++) {
            long diff = (long)original[i] - original[0];
            
            // copy[i] = copy[0] + diff
            // bounds[i][0] <= copy[0] + diff <= bounds[i][1]
            // bounds[i][0] - diff <= copy[0] <= bounds[i][1] - diff
            
            long newMin = bounds[i][0] - diff;
            long newMax = bounds[i][1] - diff;
            
            minVal = Math.Max(minVal, newMin);
            maxVal = Math.Min(maxVal, newMax);
            
            if (minVal > maxVal) {
                return 0;
            }
        }
        
        return (int)(maxVal - minVal + 1);
    }
}

var countArrays = function(original, bounds) {
    let minVal = bounds[0][0];
    let maxVal = bounds[0][1];
    
    const n = original.length;
    
    for (let i = 1; i < n; i++) {
        const diff = original[i] - original[0];
        
        // copy[i] = copy[0] + diff
        // bounds[i][0] <= copy[0] + diff <= bounds[i][1]
        // bounds[i][0] - diff <= copy[0] <= bounds[i][1] - diff
        
        const newMin = bounds[i][0] - diff;
        const newMax = bounds[i][1] - diff;
        
        minVal = Math.max(minVal, newMin);
        maxVal = Math.min(maxVal, newMax);
        
        if (minVal > maxVal) {
            return 0;
        }
    }
    
    return maxVal - minVal + 1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历数组一次，每次操作为常数时间
空间复杂度O(1)只使用常数额外空间存储范围边界

相关题目