当前位置：首页 > news >正文

LeetCode 941 有效的山脉数组

news 来源：原创 2025/9/19 16:32:13

算法探索：如何精准判断有效山脉数组

在计算机科学领域，算法和数据结构堪称基石，它们不仅是解决复杂问题的有力工具，更是衡量程序员技术水平的重要指标。数组作为最基础、应用最广泛的数据结构之一，围绕它衍生出了大量经典算法问题。今天，我们将深入剖析一道极具代表性的算法题 —— 判断一个数组是否为有效山脉数组。这道题不仅能锻炼我们对数组操作的熟练度，还能显著提升算法设计和逻辑思维能力，为攻克更复杂的编程挑战奠定坚实基础。

一、问题详细剖析

给定一个整数数组arr，我们的任务是判断它是否符合有效山脉数组的定义。一个数组要成为有效山脉数组，必须同时满足以下两个条件：

数组长度要求：数组的长度不小于 3，即arr.length >= 3。这是因为一座完整的 “山脉” 至少需要三个点，才能呈现出先上升后下降的形态。只有两个或更少元素的数组，无法形成山脉的形状。
元素趋势要求：在索引范围0 < i < arr.length - 1内，存在一个索引i，使得数组呈现出两段截然不同的趋势：
- 上升阶段：从数组起始到索引i，元素值严格递增，即arr[0] < arr[1] < ... < arr[i - 1] < arr[i]。在这个阶段，数组元素的值不断增大。
- 下降阶段：从索引i开始到数组末尾，元素值严格递减，即arr[i] > arr[i + 1] > ... > arr[arr.length - 1]。在这个阶段，数组元素的值持续减小。

为了更好地理解，我们来看几个具体例子：

有效山脉数组：对于数组[2, 4, 8, 6, 3]，长度为 5，满足arr.length >= 3。从arr[0] = 2到arr[2] = 8，元素严格递增；从arr[2] = 8到arr[4] = 3，元素严格递减，因此它是一个有效山脉数组。
无效山脉数组：对于数组[1, 2, 3, 4, 5]，虽然元素严格递增，但不存在下降阶段，不满足有效山脉数组的定义。同样，数组[5, 4, 3, 2, 1]只有下降阶段，没有上升阶段，也不是有效山脉数组。

二、解题思路深度解析

面对这一问题，关键在于准确识别出数组中的上升和下降阶段。为了有条不紊地解决问题，我们可以按照以下步骤进行：

长度检查：算法的第一步，是对数组的长度进行检查。若数组长度小于 3，根据有效山脉数组的定义，它无法形成先升后降的形态，因此可以直接判定该数组不是有效山脉数组，返回false。这一步能快速排除不符合基本条件的数组，减少后续不必要的计算。
寻找山峰：接下来，通过从左至右遍历数组，找到第一个满足arr[i] > arr[i + 1]的索引i。在遍历过程中，数组元素一直保持递增。一旦找到这样的i，就意味着我们找到了数组从上升转为下降的转折点，即潜在的 “山峰” 位置。这个过程类似于在现实中寻找山脉的山顶。
边界检查：找到潜在的 “山峰” 后，需要对其位置进行边界检查。若i等于 0，说明数组从一开始就处于下降状态，不符合山脉数组先上升的要求；若i是数组的最后一个元素，表明数组在整个遍历过程中一直处于上升状态，同样不符合山脉数组的定义。这两种情况下，都可以直接返回false。边界检查确保了我们找到的 “山峰” 在数组的合理位置。
检查下降阶段：经过前面的步骤，确认了数组存在上升阶段且 “山峰” 不在边界。下一步，从索引i开始继续遍历数组，检查后续元素是否严格递减。若后续元素始终保持递减，直至数组末尾，说明该数组符合有效山脉数组的定义，返回true；若在遍历过程中，发现有不符合递减要求的元素，即返回false。这一步验证了山脉在越过山顶后是否持续下降。

三、多语言代码实现及解析

Java 代码实现

class Solution {public boolean validMountainArray(int[] arr) {int n = arr.length;// 检查数组长度是否小于3if (n < 3) {return false;}int i = 0;// 寻找上升阶段的结束点while (i < n - 1 && arr[i] < arr[i + 1]) {i++;}// 判断山峰是否在边界if (i == 0 || i == n - 1) {return false;}// 检查下降阶段while (i < n - 1 && arr[i] > arr[i + 1]) {i++;}// 判断是否成功遍历到数组末尾return i == n - 1;}
}

四、复杂度分析

时间复杂度：在这个算法中，数组最多被遍历两次。第一次遍历用于寻找上升阶段的结束点，第二次遍历用于检查下降阶段。由于每次遍历的时间复杂度都是 $O(n)$ ，其中n是数组arr的长度，因此整个算法的时间复杂度为 $O(n)$ 。这意味着，无论数组的具体内容如何，算法的执行时间与数组的长度成正比。
空间复杂度：由于算法在执行过程中，仅使用了几个额外的变量，如n、i等，这些变量所占的空间与输入数组的大小无关。因此，算法的空间复杂度为 $O(1)$ 。这表明，无论输入数组有多大，算法所占用的额外空间都是固定的。

五、总结与拓展

判断有效山脉数组这一问题，虽然在算法设计上并不复杂，但通过对数组的遍历和条件判断，巧妙地考察了我们对数组特性和逻辑控制的掌握程度。在解题过程中，清晰的思路和细致的步骤分解是关键。这道题不仅深化了我们对数组操作的理解，更为解决更复杂的算法问题提供了重要的思维范式。

在实际编程中，类似的解题思路，如通过有序的步骤分析、边界条件的检查，将帮助我们应对各种复杂的算法挑战。此外，这道题还可以进一步拓展，例如：

变体问题：给定一个数组，寻找其中最长的有效山脉子数组。
拓展应用：在数据分析中，判断数据趋势是否符合特定的上升和下降模式。

通过不断探索和实践，我们可以更好地掌握算法设计的技巧，提升编程能力和问题解决能力。