leetcode-2145

题目

题目链接

分析

• 隐藏数组是什么？题目提供了一个difference数组，用来表示隐藏数组两个相邻元素的差值
• 隐藏数组hidden ，那么 differences[i] = hidden[i + 1] - hidden[i]
  • difference长度为n，那么hidden长度为n + 1
  • 给定lower和upper，hidden[i]的范围为[lower, upper]
• 所以，hidden的数量可以用差值的范围来表示
• 只要hidden数组的差值diff小于等于upper-lower，hidden数组的数量就是upper-lower-diff+1
  • diff如何计算？
  • 可以用前缀和来计算
  • 前缀和的定义为：prefix[i] = hidden[0] + hidden[1] + … + hidden[i]
  • 以0为起始，那么prefix[i] = prefix[i - 1] + difference[i]
  • 记录每个前缀，更新hidden数组的最大值和最小值（相对于0），就可以得到hidden数组的差值diff，和upper-lower比较即可

源代码

源代码链接