leetcode
leetcode 2051 ~ 2100
寻找可见山的数量

寻找可见山的数量

难度:

标签:

题目描述

代码结果

运行时间: 264 ms, 内存: 55.1 MB


/*
题目思路:
我们可以使用Java Stream API来简化代码实现。我们维护一个状态,记录当前最大高度,并在遍历每个山的时候更新这个状态。
解题步骤如下:
1. 使用流遍历数组并保留每一个山的高度和当前最大高度。
2. 如果当前山的高度大于前一个记录的最大高度,则将其计数。
3. 最后返回计数。
*/
import java.util.stream.IntStream;
public class Solution {
    public int countVisibleMountains(int[] heights) {
        int[] maxHeight = {0};
        return (int) IntStream.of(heights).filter(height -> {
            if (height > maxHeight[0]) {
                maxHeight[0] = height;
                return true;
            }
            return false;
        }).count();
    }
}

解释

方法:

本题解利用了区间重叠的思路来判断山峰是否可见。首先,对于每个山峰坐标(x, y),通过(x - y, x + y)来转换成一个区间。这个区间代表山峰的基底范围。接着,将所有区间按照左端点排序,如果左端点相同则按右端点排序。通过遍历排序后的区间,使用贪心算法合并所有重叠的区间,并记录无法被当前最大区间完全覆盖的区间数量。合并过程中,检查是否存在与当前区间完全相同的区间,这些相同的区间代表不可见的山峰。最后,返回不重复且可见的山峰数量。

时间复杂度:

O(n log n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么你选择使用区间(x - y, x + y)来表示山峰的可见性?这种表示有什么特别的意义吗?
使用区间(x - y, x + y)来表示山峰的可见性,是基于山峰的几何视觉投影。在二维平面上,一个位于(x, y)的山峰,其视觉影响范围可以被看作是从其顶点向左右两侧延伸的视线。这些视线在x轴上的投影就是(x - y)到(x + y)。这样的区间表示可以帮助我们理解和计算山峰之间是否存在视觉上的遮挡。如果两个山峰的区间有重叠,那么它们在视觉上至少部分是重叠的,这种转换使得问题转化为一个区间重叠问题,便于使用区间处理方法来解决。
🦆
排序区间时,为什么要首先根据左端点进行排序,如果左端点相同再根据右端点排序?这样的排序策略对算法有什么具体的影响?
在处理区间问题时,首先按照左端点进行排序是为了确定处理顺序,从最左侧开始处理可以确保我们按照从左到右的顺序查看每个区间。如果左端点相同,则根据右端点进行进一步排序,这样做的目的是在处理具有相同开始点的区间时,优先考虑那些延伸得更远的区间。这种排序策略有助于简化区间合并的逻辑,因为一旦确定了开始处理某个左端点的区间,我们可以便捷地通过比较右端点来判断区间之间的重叠和包含关系。这种策略对算法的主要影响是提高了处理的效率和准确性,使得合并区间的过程更加直观和系统化。
🦆
解中提到使用贪心算法合并重叠的区间,能否详细解释一下这里所说的'贪心'策略是如何应用的?
贪心算法在这个问题中的应用表现在合并区间的过程中。具体来说,当我们遇到一个新的区间时,我们会检查这个区间与当前合并区间(即已经合并的区间中最大的区间)的关系。如果新区间与当前合并区间重叠(即新区间的左端点小于等于当前合并区间的右端点),我们会更新当前合并区间的右端点为两个区间右端点的最大值。这个过程一直持续,直到没有更多的重叠发生,然后将当前合并区间视为一个独立的可见区间,并开始一个新的合并区间。这种方法是贪心的,因为它在每一步总是尝试扩展当前区间以包含尽可能多的后续区间,而不考虑未来可能出现的更优区间组合。这种策略在很多区间合并问题中都是有效的,因为它在每一步都做出了局部最优的选择。

相关问题