【数据结构和算法】找到最高海拔

目录

其他系列文章导航

Java基础合集
数据结构与算法合集

设计模式合集

多线程合集

分布式合集

ES合集

文章目录

其他系列文章导航

文章目录

前言

一、题目描述

二、题解

2.1 前缀和的解题模板

2.1.1 最长递增子序列长度

2.1.2 寻找数组中第 k 大的元素

2.1.3 最长公共子序列长度

2.1.4 寻找数组中第 k 小的元素

2.2 方法一：前缀和（差分数组）

三、代码

3.2 方法一：前缀和（差分数组）

四、复杂度分析

4.2 方法一：前缀和（差分数组）

前言

这是力扣的 1732 题，难度为简单，解题方案有很多种，本文讲解我认为最奇妙的一种。

这是一道非常经典的前缀和问题，虽然看似简单，但它却能让你深入理解前缀和的特点。

一、题目描述

有一个自行车手打算进行一场公路骑行，这条路线总共由 n + 1 个不同海拔的点组成。自行车手从海拔为 0 的点 0 开始骑行。

给你一个长度为 n 的整数数组 gain ，其中 gain[i] 是点 i 和点 i + 1 的 净海拔高度差（0 <= i < n）。请你返回 最高点的海拔 。

示例 1：

输入：gain = [-5,1,5,0,-7]
输出：1
解释：海拔高度依次为 [0,-5,-4,1,1,-6] 。最高海拔为 1 。

示例 2：

输入：gain = [-4,-3,-2,-1,4,3,2]
输出：0
解释：海拔高度依次为 [0,-4,-7,-9,-10,-6,-3,-1] 。最高海拔为 0 。

提示：

• n == gain.length
• 1 <= n <= 100
• -100 <= gain[i] <= 100

二、题解

2.1 前缀和的解题模板

前缀和算法是一种在处理数组或链表问题时常用的技巧，它可以有效地减少重复计算，提高算法的效率。下面是一些常见的使用前缀和算法的题目以及解题思路：

2.1.1 最长递增子序列长度

题目描述：给定一个无序数组，求最长递增子序列的长度。

解题思路：可以使用前缀和和单调栈来解决这个问题。首先，遍历数组，计算出前缀和。然后，使用单调栈记录当前递增子序列的起始位置。遍历数组时，如果当前元素大于前缀和，说明可以扩展当前递增子序列，将当前位置入栈。如果当前元素小于等于前缀和，说明当前递增子序列已经结束，弹出栈顶元素。最后，栈中剩余的元素即为最长递增子序列的起始位置，计算长度即可。

2.1.2 寻找数组中第 k 大的元素

题目描述：给定一个无序数组和一个整数k，找到数组中第k大的元素。

解题思路：可以使用前缀和和快速选择算法来解决这个问题。首先，计算出数组的前缀和。然后，使用快速选择算法在数组中找到第k小的元素。具体实现中，每次选择一个枢轴元素，将数组分成两部分，小于枢轴的元素和大于枢轴的元素。如果枢轴左边的元素个数小于k，则在左边的子数组中继续查找；如果枢轴左边的元素个数大于等于k，则在右边的子数组中继续查找。最后，当找到第k小的元素时，返回该元素即可。

2.1.3 最长公共子序列长度

题目描述：给定两个字符串，求最长公共子序列的长度。

解题思路：可以使用动态规划算法来解决这个问题。如果字符串长度分别为m和n，则可以定义一个二维数组dp[m+1][n+1]，其中dp[i][j]表示字符串s1的前i个字符和字符串s2的前j个字符的最长公共子序列长度。根据动态规划的思想，状态转移方程为dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])。如果s1[i-1]等于s2[j-1]，则dp[i][j] = dp[i-1][j-1] + 1；否则dp[i][j]取其他两种情况中的较大值。最终结果为dp[m][n]。

2.1.4 寻找数组中第 k 小的元素

题目描述：给定一个无序数组和一个整数k，找到数组中第k小的元素。

解题思路：可以使用前缀和和快速选择算法来解决这个问题。具体实现与寻找第k大元素类似，只不过最后返回的是第k小的元素而非第k大的元素。

2.2 方法一：前缀和（差分数组）

解这个问题需要注意以下几点：

1. 理解题意：首先，要明确题目的要求，理解自行车手的骑行路线和海拔变化的关系。根据题目描述，自行车手从海拔为0的点开始骑行，通过一系列的海拔变化，最终要找到最高点的海拔。
2. 分析海拔变化：根据给定的gain数组，可以分析出自行车手的海拔变化。gain[i]表示点i和点i+1之间的净海拔高度差。通过累加这些高度差，可以计算出经过每个点后的总海拔变化。
3. 确定最高点的海拔：在计算出总的海拔变化后，需要找到最高点的海拔。这可以通过比较累加海拔和初始海拔的大小来实现。最高点的海拔即为累加海拔和初始海拔中的较大值。
4. 注意数组边界条件：在处理gain数组时，需要注意数组的边界条件。例如，gain[0]表示起点和终点之间的海拔高度差，而gain[n-1]表示倒数第二个点和终点之间的海拔高度差。
5. 代码实现：最后，根据上述分析，可以使用Python等编程语言实现相应的算法。在实现过程中，需要注意代码的简洁性和可读性，同时也要注意处理可能的异常情况。

思路与算法：

我们假设每个点的海拔为 hi ，由于 gain[i] 表示第 i 个点和第 i+1 个点的海拔差，因此

gain[i] = h（i+1) − hi，那么： 

可以发现，每个点的海拔都可以通过前缀和的方式计算出来。因此，我们只需要遍历一遍数组，求出前缀和的最大值，即为最高点的海拔。

实际上题目中的 gain 数组是一个差分数组，对差分数组求前缀和即可得到原海拔数组。然后求出原海拔数组的最大值即可。

三、代码

3.2 方法一：前缀和（差分数组）

Java版本：

class Solution {
    public int largestAltitude(int[] gain) {
    int high = 0, max = 0;
        for (int h : gain) {
            high += h;
            max = Math.max(max, high);
        }
        return max;
    }
}

C++版本：

class Solution {
public:
    int largestAltitude(std::vector<int>& gain) {
        int high = 0, max = 0;
        for (int h : gain) {
            high += h;
            max = std::max(max, high);
        }
        return max;
    }
};

Python版本：

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        high = 0
        max_altitude = 0
        for h in gain:
            high += h
            max_altitude = max(max_altitude, high)
        return max_altitude

Go版本：

func largestAltitude(gain []int) int {
    high, max := 0, 0
    for _, h := range gain {
        high += h
        if high > max {
            max = high
        }
    }
    return max
}

func main() {
    gain := []int{-5, 1, 5, 0, -7}
    result := largestAltitude(gain)
    fmt.Println(result)
}

四、复杂度分析

4.2 方法一：前缀和（差分数组）

• 时间复杂度： O(n)，其中 n 为数组 gain 的长度。
• 空间复杂度： O(1)。