如何用Dart/Flutter求解最少需补充的雕像数量问题？

题目说明 #

示例 #

当statues = [6, 2, 3, 8]时，输出应为
solution(statues) = 3。

需要补充尺寸为4、5和7的雕像。

输入输出规范 #

• 执行时间限制：4秒（JS）
• 输入：List<int> statues
  由不同非负整数组成的数组，满足：

  1 ≤ statues.length ≤ 10,
  0 ≤ statues[i] ≤ 20.

• 输出：int
  为让现有雕像覆盖连续整数区间[L, R]（无遗漏、无额外），需要添加的最少雕像数量。

Dart实现方案 #

核心思路 #

要覆盖连续区间，先确定现有雕像的最小和最大尺寸，计算该区间内所有整数的总数，减去现有雕像的数量，差值就是需要补充的雕像数。

代码实现 #

int solution(List<int> statues) {
  // 找出数组中的最小和最大值
  final minStatue = statues.reduce((a, b) => a < b ? a : b);
  final maxStatue = statues.reduce((a, b) => a > b ? a : b);
  // 区间总整数数减去现有雕像数，得到需要补充的数量
  return (maxStatue - minStatue + 1) - statues.length;
}

// 测试示例
void main() {
  print(solution([6, 2, 3, 8])); // 输出：3
}

代码解释 #

1. 找极值：通过reduce方法遍历数组，分别得到最小和最大的雕像尺寸，明确需要覆盖的连续区间范围。
2. 计算区间总数：区间[min, max]内的整数总数为max - min + 1（包含两端数值）。
3. 求缺失数量：用区间总数减去现有雕像的数量，结果就是需要添加的最少雕像数。

内容的提问来源于stack exchange，提问作者shahzad_c9