Facing The Sun Problem in Java

“面向太阳”问题 涉及确定一排建筑中可以看到太阳的建筑数量，假设阳光来自特定方向（通常是左侧）。每栋建筑的高度都会影响可见性，因此这是一个通常需要遍历和比较技术才能有效解决的问题。

示例

输入 [4, 2, 3, 1, 5]

输出 2

解释

第一栋建筑（高度 4）可以看到太阳，因为它最初是最高的。第二栋建筑（高度 2）较矮且被遮挡。第三栋建筑（高度 3）也被第一栋较高的建筑遮挡。第五栋建筑（高度 5）比所有之前的建筑都高，可以看到太阳。

使用贪心算法

算法

步骤 1：理解问题： 我们需要确定当阳光从左侧照射时，有多少栋建筑可以看到太阳。如果一栋建筑比它前面的建筑都高，那么它就能看到太阳。

步骤 1.1：分析输入和输出： 首先，检查输入，它是一个建筑高度的数组。每个高度代表一排建筑的大小。输出是可以看到太阳的建筑数量，考虑到阳光来自左侧。如果一栋建筑比它前面的所有建筑都高，那么它就能看到太阳。

步骤 2：初始化变量： 创建一个 变量 `maxHeight` 并将其设置为 0。它将存储遇到的最高建筑高度。创建一个变量 `count` 并将其设置为 0。它将跟踪可以看到太阳的建筑数量。

步骤 2.1：设置初始条件： 在遍历建筑之前，将 `max-height` 的初始值设置为 0，因为还没有遇到任何建筑。这将有助于确定哪些建筑比迄今为止遇到的最高建筑更高。将 `count` 变量设置为 1，因为第一栋建筑总是可以看到太阳。

步骤 3：遍历数组： 从左到右遍历建筑高度的数组。

步骤 3.1： 对于每栋建筑，将其高度与其 `maxHeight` 进行比较。如果当前建筑的高度大于 `maxHeight`，则它可以看到太阳。将 `maxHeight` 更新为当前建筑的高度。将 `count` 增加 1。

步骤 4：返回结果： 遍历完整个 数组 后，`count` 将包含可以看到太阳的建筑总数。

步骤 4.1：处理边缘情况： 在返回结果之前，处理任何边缘情况。例如，如果输入数组为空，则返回 0，因为没有建筑可以看到太阳。同样，如果数组只包含一栋建筑，它总是会被计数，因为它将是该排中的最高建筑。

步骤 5：输出结果： 完成迭代后，`count` 变量保存可以看到太阳的建筑数量。将此值作为结果返回或打印。它是最终输出，指示该排中有多少建筑可以看到无遮挡的阳光。

文件名：FacingTheSun.java

输出

 
2   

复杂度分析

时间复杂度

该算法只遍历一次建筑高度数组，为每栋建筑执行一次常数时间的比较和更新。因此，时间复杂度为 O(n)，其中 n 是建筑数量。它确保了解决方案的效率，时间复杂度与输入大小成线性关系。

空间复杂度

此解决方案的空间复杂度为 O(1)，因为它只使用恒定的额外空间，而与输入大小无关。`maxHeight` 和 `count` 变量是仅需的额外存储，因此空间复杂度与建筑数量无关。

使用堆栈

算法

步骤 1：理解问题： 想象一下建筑排成一条直线。阳光从左边照射。一栋建筑只有在其左边的所有建筑都比它矮时才能看到太阳。您的任务是根据此条件计算可以看到太阳的建筑数量。

步骤 2：规划方法： 要确定哪些建筑可以看到太阳，我们需要：跟踪当前“未被遮挡”的建筑的高度。使用一个结构（在本例中为堆栈）来存储在遍历数组时的高度。仅当一栋建筑比它前面的所有建筑都高时，才将其添加到堆栈中。

步骤 3：设置解决方案： 初始化一个空堆栈：堆栈将存储可以看到太阳的建筑的高度。从该排的第一栋建筑开始，按顺序处理每一栋建筑。

步骤 3.1：初始化用于跟踪的变量： 在开始遍历之前，请确保所有必需的变量都已准备好。例如，定义用于存储建筑高度的堆栈以及用于保存可见建筑的最终计数的变量。此设置确保了下一步的结构化和高效流程。

步骤 4：遍历高度数组： 对于数组中的每栋建筑：检查堆栈是否为空：如果堆栈为空，则表示尚未处理任何建筑。将第一栋建筑的高度添加到堆栈中，因为它总是可以看到太阳。

步骤 4.1：将当前高度与堆栈顶部进行比较： 如果当前建筑的高度大于堆栈顶端的高度，则这栋建筑可以看到太阳。将其添加到堆栈中。

如果当前高度小于或等于堆栈顶部的高度，则该建筑被遮挡，无法看到太阳，将其忽略。对数组中的每栋建筑重复此过程。

步骤 5：计算建筑数量： 处理完所有建筑后：可以看到太阳的建筑数量等于堆栈中的高度数量。将堆栈的大小作为结果返回。

步骤 5.1：确保所有有效建筑都已计数： 遍历数组后，请确认堆栈中仅留下代表可以看到太阳的建筑的高度。这些高度必须从左到右严格递增，以确保没有较矮的建筑遮挡已添加的较高建筑。堆栈的大小反映了未被遮挡的建筑的最终数量。

步骤 6：处理边缘情况：无建筑（空数组）： 如果输入数组为空，则返回 0，因为没有建筑可以看到太阳。

单栋建筑： 如果只有一栋建筑，它总是可以看到太阳。返回 1。所有相同高度的建筑： 该排中只有第一栋建筑可以看到太阳，因为相同高度的后续建筑将被遮挡。

文件名：FacingTheSun.java

输出

 
2   

复杂度分析

时间复杂度

基于堆栈的方法的时间复杂度为 O(n)，其中 n 是建筑数量。在遍历数组时，每栋建筑都恰好处理一次。堆栈操作（push 和 peek）是常数时间，因此总体复杂度保持线性，确保了对大型输入的效率。

空间复杂度

基于堆栈的方法的空间复杂度为 O(n)，其中 n 是建筑数量。在最坏的情况下，如果每栋建筑都比前一栋高，则所有建筑都可能被添加到堆栈中。因此，堆栈需要与输入大小成比例的空间进行存储。