leetcode
leetcode 1701 ~ 1750
街上最亮的位置

街上最亮的位置

难度:

标签:

题目描述

代码结果

运行时间: 256 ms, 内存: 59.2 MB


/*
 * 思路:
 * 使用Java Stream处理数据,我们将街道表示为一个数组,并使用流来处理亮度的增加和寻找最亮点。
 */
import java.util.stream.IntStream;

public class BrightestPositionStream {
    public static int findBrightestPosition(int[] lights, int[] ranges) {
        int[] street = new int[1001]; // 假设街道的长度为1000

        // 使用流处理每个灯的亮度增加
        IntStream.range(0, lights.length).forEach(i -> {
            int start = Math.max(0, lights[i] - ranges[i]);
            int end = Math.min(1000, lights[i] + ranges[i]);
            IntStream.rangeClosed(start, end).forEach(j -> street[j]++);
        });

        // 使用流找到最大亮度的位置
        return IntStream.range(0, street.length)
                .reduce((i, j) -> street[i] >= street[j] ? i : j)
                .orElse(0);
    }
}

解释

方法:

本题解采用了扫描线算法的思路,处理街道上的灯光问题。每个灯都有一个中心位置和照射范围,题解通过记录每个灯照射开始和结束后的位置增减变化,使用一个计数器(counter)累计每个位置的灯光影响。具体步骤如下: 1. 对于每个灯光,计算其影响开始的位置(it[0] - it[1])和影响结束的下一个位置(it[0] + it[1] + 1),分别在计数器中增加和减少影响。 2. 对所有关键点(灯光影响的开始和结束位置)进行排序,并遍历它们。 3. 使用累加变量(acc)来维护当前位置的总照明强度,并在遍历过程中更新记录最大照明强度及其位置。 4. 最终,返回拥有最大照明强度的位置。

时间复杂度:

O(n log n)

空间复杂度:

O(n)

代码细节讲解

🦆
扫描线算法中的`计数器`具体是如何工作的?是如何确保它能准确记录每个位置的照明变化的?
扫描线算法中的`计数器`是通过一个哈希表(在 Python 中通常使用 defaultdict)来实现的。这个计数器对每个关键位置(灯光的开始和结束位置的下一个位置)记录一个增减值。当灯光开始照射时,该位置的计数增加;而在灯光结束后的下一个位置,计数减少。这种方法可以在遍历这些关键点并累加这些变化值时,动态地计算出任何给定位置的总照明强度。这确保了计数器可以准确地反映出每个位置的实时照明情况。
🦆
请问在处理灯光影响范围时,为什么选择在结束位置的下一个位置减1而不是直接在结束位置减1?
在处理灯光的影响范围时,选择在结束位置的下一个位置减1而不是直接在结束位置减1,是为了正确处理灯光的覆盖区间。这种做法基于区间的开闭原则(左闭右开),即包括开始位置但不包括结束位置的下一个位置。这样,在结束位置的灯光仍然有效,只有到了结束位置的下一个位置,灯光效果才真正结束。这种处理避免了灯光结束边界的重叠误差,使得每个灯光的影响范围被准确地计算。
🦆
算法中的排序步骤是否会影响整体性能?在最坏的情况下,这种排序的时间复杂度是多少?
算法中的排序步骤确实会影响整体性能,因为它决定了遍历关键点的顺序。在本算法中,所有灯光的开始位置和结束后的下一个位置都被记录并需要排序。排序这些关键点是必须的,以确保我们可以按顺序更新和计算每个位置的照明强度。在最坏的情况下,如果所有的灯光都有不同的开始和结束位置,排序的时间复杂度为O(n log n),其中n是关键点的数量。由于每个灯光贡献了两个关键点(开始和结束的下一个位置),因此关键点的总数大约是灯光数量的两倍。因此,排序步骤在数据量大时可能成为性能瓶颈。

相关问题