难度: Medium
Submission
运行时间: 264 ms
内存: 55.1 MB
class Solution:
def visibleMountains(self, peaks: List[List[int]]) -> int:
intervals = [(x - y, x + y) for x, y in peaks]
intervals.sort(key = lambda x:(x[0], x[1]))
cnt = 0
i = 0
n = len(intervals)
while i < n:
l, r = intervals[i]
j = i + 1
identify = False
while j < n and intervals[j][1] <= r:
cl, cr = intervals[j]
if cl == l and cr == r:
identify = True
j += 1
i = j
if identify or (j < n and intervals[j][0] == l):
continue
cnt += 1
return cnt
Explain
本题解利用了区间重叠的思路来判断山峰是否可见。首先，对于每个山峰坐标(x, y)，通过(x - y, x + y)来转换成一个区间。这个区间代表山峰的基底范围。接着，将所有区间按照左端点排序，如果左端点相同则按右端点排序。通过遍历排序后的区间，使用贪心算法合并所有重叠的区间，并记录无法被当前最大区间完全覆盖的区间数量。合并过程中，检查是否存在与当前区间完全相同的区间，这些相同的区间代表不可见的山峰。最后，返回不重复且可见的山峰数量。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def visibleMountains(self, peaks: List[List[int]]) -> int:
# 创建区间，每个山峰对应一个区间
intervals = [(x - y, x + y) for x, y in peaks]
# 根据区间的左端点排序，如果相同则根据右端点排序
intervals.sort(key=lambda x: (x[0], x[1]))
cnt = 0
i = 0
n = len(intervals)
# 遍历所有区间，合并重叠的区间
while i < n:
l, r = intervals[i]
j = i + 1
identify = False
# 检查当前区间与后续区间是否重叠或完全相同
while j < n and intervals[j][1] <= r:
cl, cr = intervals[j]
if cl == l and cr == r:
identify = True
j += 1
i = j
# 如果当前区间完全相同或者右端点相同，则跳过当前区间
if identify or (j < n and intervals[j][0] == l):
continue
# 否则，当前区间为可见的山峰
cnt += 1
return cnt
Explore
使用区间(x - y, x + y)来表示山峰的可见性，是基于山峰的几何视觉投影。在二维平面上，一个位于(x, y)的山峰，其视觉影响范围可以被看作是从其顶点向左右两侧延伸的视线。这些视线在x轴上的投影就是(x - y)到(x + y)。这样的区间表示可以帮助我们理解和计算山峰之间是否存在视觉上的遮挡。如果两个山峰的区间有重叠，那么它们在视觉上至少部分是重叠的，这种转换使得问题转化为一个区间重叠问题，便于使用区间处理方法来解决。
在处理区间问题时，首先按照左端点进行排序是为了确定处理顺序，从最左侧开始处理可以确保我们按照从左到右的顺序查看每个区间。如果左端点相同，则根据右端点进行进一步排序，这样做的目的是在处理具有相同开始点的区间时，优先考虑那些延伸得更远的区间。这种排序策略有助于简化区间合并的逻辑，因为一旦确定了开始处理某个左端点的区间，我们可以便捷地通过比较右端点来判断区间之间的重叠和包含关系。这种策略对算法的主要影响是提高了处理的效率和准确性，使得合并区间的过程更加直观和系统化。
贪心算法在这个问题中的应用表现在合并区间的过程中。具体来说，当我们遇到一个新的区间时，我们会检查这个区间与当前合并区间（即已经合并的区间中最大的区间）的关系。如果新区间与当前合并区间重叠（即新区间的左端点小于等于当前合并区间的右端点），我们会更新当前合并区间的右端点为两个区间右端点的最大值。这个过程一直持续，直到没有更多的重叠发生，然后将当前合并区间视为一个独立的可见区间，并开始一个新的合并区间。这种方法是贪心的，因为它在每一步总是尝试扩展当前区间以包含尽可能多的后续区间，而不考虑未来可能出现的更优区间组合。这种策略在很多区间合并问题中都是有效的，因为它在每一步都做出了局部最优的选择。