candles专题

Leetcode 2055. Plates Between Candles [Python]

第一种前缀和加二分搜索,会TLE。这里着重看第二种方法的思路,前缀和从左到右做一次,然后以“|”蜡烛位置为标杆,将一颗蜡烛位置之前的盘子数量统一,也就是例如,到地3颗蜡烛,共有5个盘子,而到第二颗蜡烛之前,有2颗盘子,则把第3颗蜡烛到第三颗蜡烛之间的盘子数和都记做5.因为题目要求只看start右侧最近的蜡烛之后的盘子。同理,只看end左侧最近的蜡烛之前的盘子。这里,把“s”颠倒,重复上述前缀和以及