假设我们有一个称为nums的数字列表和一个操作列表。在这里,每个运算都有三个字段[L,R,X],这表明我们应将所有从索引L到R(包括索引)的元素加X。我们必须应用所有操作并返回最终列表。
因此,如果输入像nums = [8,4,2,-9,4]运算= [[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]。
为了解决这个问题,我们将遵循以下步骤-
事件:=一个新列表
对于操作中的每个(l,r,inc),执行
在事件结束时插入(l,inc)
在事件结束时插入(r + 1,-inc)
排序列表事件
inc:= 0,ptr:= 0
对于范围从0到nums的i,执行
inc:= inc + events [ptr,1]
点:=点+ 1
而ptr <事件和events [ptr,0]的大小与i相同,
nums [i]:= nums [i] + inc
返回数字
让我们看下面的实现以更好地理解-
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))
[1,2,3,4,5,6,7,8,9,10], 3
输出结果
[11, 6, 9, -2, 4]