用 Python 编写程序来更新给定范围内的元素

pythonserver side programmingprogramming更新于 2026/2/2 14:04:17

假设我们有一个名为 nums 的数字列表和一个操作列表。这里每个操作都有三个字段 [L、R、X]，这表示我们应该将索引从 L 到 R(含)的所有元素增加 X。我们必须应用所有操作并返回最终列表。

因此，如果输入类似于 nums = [8, 4, 2, -9, 4] operations = [ [0, 0, 3], [1, 3, 2], [2, 3, 5] ]，则输出将为 [11, 6, 9, -2, 4]，因为初始列表为 [8, 4, 2, -9, 4]。

执行第一个操作 [0, 0, 3] 时列表将为 [11, 4, 2, -9, 4]。
执行第一个操作 [1, 3, 2] 时列表将为 [11, 6, 4, -7, 4]。
执行第一个操作 [2, 3, 5] 时列表将为 [11, 6, 9, -2, 4]。

为了解决这个问题，我们将遵循以下步骤 −

events := a new list
对于操作中的每个 (l, r, inc)，执行
- 在 events 末尾插入 (l, inc)
- 在 events 末尾插入 (r + 1, -inc)
对 events 列表进行排序
inc := 0, ptr := 0
对于范围从 0 到 nums 大小的 i，执行
- 当 ptr < 事件大小且 events[ptr, 0] 与 i 相同时，执行
  - inc := inc + events[ptr, 1]
  - ptr := ptr + 1
- nums[i] := nums[i] + inc
返回 nums

让我们看看下面的实现以便更好地理解 −

示例

class Solution:
   def solve(self, nums, operations):
      events = []
      for l, r, inc in operations:
         events.append((l, inc))
         events.append((r + 1, -inc))
      events.sort()
      inc = 0
      ptr = 0
      for i in range(len(nums)):
         while ptr < len(events) and events[ptr][0] == i:
            inc += events[ptr][1]
            ptr += 1
         nums[i] += inc
      return nums
ob = Solution()
nums = [8, 4, 2, -9, 4]
operations = [ [0, 0, 3], [1, 3, 2], [2, 3, 5] ]
print(ob.solve(nums, operations))