Leetcode-2145-统计隐藏数组数目

题目

给你一个下标从 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 。

分析

由于满足要求的数组长度为n+1，故可以设满足要求的数组为 $a[0], a[1], a[2], ..., a[n]$

由关系式

$diff[i] = a[i+1] - a[i]$

可得

$diff[0] = a[1] - a[0] \\ diff[1] = a[2] - a[1] \\ diff[2] = a[3] - a[2] \\ ... \\ diff[n-2] = a[n-1] - a[n-2] \\ diff[n-1] = a[n] - a[n-1]$

观察可以发现：

$diff[1]+diff[2]=a[3]-a[1]$

对于任意的i,j如果满足 $0 \le i, j \le n$，则有以下关系成立：

$a[j] - a[i] = \sum_{k=i}^{j-1} diff[k]$

设hidden数组的最小值为$a[i]$，最大值为$a[j]$，则必定也满足:

$a[j] - a[i] = \sum_{k=i}^{j-1} diff[k]$

• 对于hidden数组中的任意一个元素m，取值范围有$m \ge lower$
• 当m取得最小值$m=lower$时候，数组中最大值元素为$m+(a[j]- [i])$
• 最大值不能超过上界upper，则有$m+(a[j]-a[i]) \le upper$
• 故m的取值上限为$m \le upper - (a[j]-a[i])$
• 即 $lower \le m \le upper - (a[j]-a[i])$
• 则总计可以取到上界-下界+1个这样的m，即$upper - (a[j]-a[i]) - lower + 1 = (upper - lower) - (a[j]-a[i]) + 1$

实现

class Solution {
public:
    int numberOfArrays(vector<int>& differences, int lower, int upper) {
        int a_min = 0, a_max = 0; // 还原整个数组a的过程中记录a的最小和最大值
        int cur = 0; // 选定一个常数标记a[0]起始值
        for (int diff: differences) {
            cur += diff; 

            // 求出最小最大值
            a_min = min(a_min, cur);
            a_max = max(a_max, cur); 

            // 若此时满足了这个条件，则不存在这样的hidden数组
            if (a_max - a_min > upper - lower) {
                return 0;
            }
        }
        return (upper - lower) - (a_max - a_min) + 1;
    }
};