编写replacedList函数：相邻元素和≤max时替换为和（仅遍历一次）

问题描述 #

给定整数数组inputList和整数max，编写函数replacedList，遍历数组一次，将每对相邻元素在其和不超过max时替换为该和；若没有符合条件的元素对，则输出原数组。

示例 #

• 输入：replacedList(5, [5, 1, 3, 3, 4])，输出：[5, 4, 3, 4]（仅1+3≤5符合条件）
• 输入：replacedList(6, [2, 3, 1, 5, 4, 3])，输出：[5, 6, 4, 3]（2+3和1+5均≤6符合条件）

代码实现 #

List<int> replacedList(int max, List<int> inputList) {
  List<int> outputList = [];
  int i = 0;
  // 一次遍历处理元素
  while (i < inputList.length) {
    // 检查是否存在相邻元素且和符合要求
    if (i + 1 < inputList.length && inputList[i] + inputList[i+1] <= max) {
      // 合并相邻元素并加入结果
      outputList.add(inputList[i] + inputList[i+1]);
      i += 2; // 跳过已合并的下一个元素
    } else {
      // 无法合并，直接加入当前元素
      outputList.add(inputList[i]);
      i += 1;
    }
  }
  return outputList;
}

void main() {
  print(replacedList(5, [5, 1, 3, 3, 4])); // 输出: [5, 4, 3, 4]
  print(replacedList(6, [2, 3, 1, 5, 4, 3])); // 输出: [5, 6, 4, 3]
}

逻辑说明 #

1. 用while循环配合索引i控制遍历进度，确保只扫描数组一次，时间复杂度为O(n)
2. 每次遍历优先检查当前元素与下一个元素的和是否满足≤max的条件：
   • 满足则合并两元素，直接将和加入结果列表，索引跳2位跳过已处理的相邻元素
   • 不满足则直接将当前元素加入结果列表，索引移1位继续处理下一个元素
3. 遍历完成后返回结果列表，自然覆盖“无符合条件元素对则输出原数组”的情况

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