难度: Medium
Submission
运行时间: 256 ms
内存: 59.2 MB
class Solution:
def brightestPosition(self, lights: List[List[int]]) -> int:
counter = defaultdict(int)
for it in lights:
counter[it[0] - it[1]] += 1
counter[it[0] + it[1]+1] -= 1
acc = 0
result = 0
count = 0
for light in sorted(counter.keys()):
acc += counter[light]
if acc > count:
result = light
count = acc
# print(count)
return result
Explain
本题解采用了扫描线算法的思路，处理街道上的灯光问题。每个灯都有一个中心位置和照射范围，题解通过记录每个灯照射开始和结束后的位置增减变化，使用一个计数器(counter)累计每个位置的灯光影响。具体步骤如下: 1. 对于每个灯光，计算其影响开始的位置(it[0] - it[1])和影响结束的下一个位置(it[0] + it[1] + 1)，分别在计数器中增加和减少影响。 2. 对所有关键点(灯光影响的开始和结束位置)进行排序，并遍历它们。 3. 使用累加变量(acc)来维护当前位置的总照明强度，并在遍历过程中更新记录最大照明强度及其位置。 4. 最终，返回拥有最大照明强度的位置。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def brightestPosition(self, lights: List[List[int]]) -> int:
counter = defaultdict(int) # 用于记录每个位置的灯光变化值
for it in lights:
counter[it[0] - it[1]] += 1 # 灯光影响开始位置的计数加1
counter[it[0] + it[1]+1] -= 1 # 灯光影响结束后的下一个位置计数减1
acc = 0 # 当前位置的累计照明强度
result = 0 # 记录最亮位置
count = 0 # 最大的照明强度
for light in sorted(counter.keys()): # 对所有影响的位置排序后遍历
acc += counter[light] # 更新当前位置的照明强度
if acc > count: # 如果当前位置的照明强度大于已记录的最大强度
result = light # 更新最亮位置
count = acc # 更新最大照明强度
return result
Explore
扫描线算法中的`计数器`是通过一个哈希表（在 Python 中通常使用 defaultdict）来实现的。这个计数器对每个关键位置（灯光的开始和结束位置的下一个位置）记录一个增减值。当灯光开始照射时，该位置的计数增加；而在灯光结束后的下一个位置，计数减少。这种方法可以在遍历这些关键点并累加这些变化值时，动态地计算出任何给定位置的总照明强度。这确保了计数器可以准确地反映出每个位置的实时照明情况。
在处理灯光的影响范围时，选择在结束位置的下一个位置减1而不是直接在结束位置减1，是为了正确处理灯光的覆盖区间。这种做法基于区间的开闭原则（左闭右开），即包括开始位置但不包括结束位置的下一个位置。这样，在结束位置的灯光仍然有效，只有到了结束位置的下一个位置，灯光效果才真正结束。这种处理避免了灯光结束边界的重叠误差，使得每个灯光的影响范围被准确地计算。
算法中的排序步骤确实会影响整体性能，因为它决定了遍历关键点的顺序。在本算法中，所有灯光的开始位置和结束后的下一个位置都被记录并需要排序。排序这些关键点是必须的，以确保我们可以按顺序更新和计算每个位置的照明强度。在最坏的情况下，如果所有的灯光都有不同的开始和结束位置，排序的时间复杂度为O(n log n)，其中n是关键点的数量。由于每个灯光贡献了两个关键点（开始和结束的下一个位置），因此关键点的总数大约是灯光数量的两倍。因此，排序步骤在数据量大时可能成为性能瓶颈。