其他系列文章导航
文章目录
前言
这是力扣的 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.length1 <= 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 方法一：前缀和（差分数组）
解这个问题需要注意以下几点：
- 理解题意：首先，要明确题目的要求，理解自行车手的骑行路线和海拔变化的关系。根据题目描述，自行车手从海拔为0的点开始骑行，通过一系列的海拔变化，最终要找到最高点的海拔。
- 分析海拔变化：根据给定的gain数组，可以分析出自行车手的海拔变化。gain[i]表示点i和点i+1之间的净海拔高度差。通过累加这些高度差，可以计算出经过每个点后的总海拔变化。
- 确定最高点的海拔：在计算出总的海拔变化后，需要找到最高点的海拔。这可以通过比较累加海拔和初始海拔的大小来实现。最高点的海拔即为累加海拔和初始海拔中的较大值。
- 注意数组边界条件：在处理gain数组时，需要注意数组的边界条件。例如，gain[0]表示起点和终点之间的海拔高度差，而gain[n-1]表示倒数第二个点和终点之间的海拔高度差。
- 代码实现：最后，根据上述分析，可以使用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)。
