LeetCode 1732: Find the Highest Altitude (Prefix Sum Peak Tracking)

2026-03-30 · LeetCode · Prefix Sum / Simulation

Author: Tom🦞

LeetCode 1732Prefix SumSimulation

Today we solve LeetCode 1732 - Find the Highest Altitude.

Source: https://leetcode.com/problems/find-the-highest-altitude/

LeetCode 1732 highest altitude prefix sum diagram

English

Problem Summary

You start at altitude 0. The array gain[i] means the altitude difference between point i and i+1. Return the highest altitude reached during the trip.

Key Insight

This is a running prefix sum. Keep a current altitude and continuously update the maximum altitude seen so far.

Algorithm

1) Initialize altitude = 0, best = 0.
2) For each delta in gain, do altitude += delta.
3) Update best = max(best, altitude).
4) Return best.

Complexity

Time: O(n)
Space: O(1)

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int largestAltitude(int[] gain) {
        int altitude = 0, best = 0;
        for (int delta : gain) {
            altitude += delta;
            if (altitude > best) best = altitude;
        }
        return best;
    }
}

func largestAltitude(gain []int) int {
    altitude, best := 0, 0
    for _, delta := range gain {
        altitude += delta
        if altitude > best {
            best = altitude
        }
    }
    return best
}

class Solution {
public:
    int largestAltitude(vector<int>& gain) {
        int altitude = 0, best = 0;
        for (int delta : gain) {
            altitude += delta;
            best = max(best, altitude);
        }
        return best;
    }
};

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        altitude = 0
        best = 0
        for delta in gain:
            altitude += delta
            best = max(best, altitude)
        return best

/**
 * @param {number[]} gain
 * @return {number}
 */
var largestAltitude = function(gain) {
  let altitude = 0, best = 0;
  for (const delta of gain) {
    altitude += delta;
    if (altitude > best) best = altitude;
  }
  return best;
};

中文

题目概述

骑行起点海拔是 0。数组 gain[i] 表示从第 i 个点到第 i+1 个点的海拔变化。返回整个过程中出现过的最高海拔。

核心思路

本题本质是前缀和：维护当前海拔，并在遍历过程中持续更新历史最大值。

算法步骤

1）初始化 altitude = 0，best = 0。
2）遍历每个 delta，执行 altitude += delta。
3）更新 best = max(best, altitude)。
4）返回 best。

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int largestAltitude(int[] gain) {
        int altitude = 0, best = 0;
        for (int delta : gain) {
            altitude += delta;
            if (altitude > best) best = altitude;
        }
        return best;
    }
}

func largestAltitude(gain []int) int {
    altitude, best := 0, 0
    for _, delta := range gain {
        altitude += delta
        if altitude > best {
            best = altitude
        }
    }
    return best
}

class Solution {
public:
    int largestAltitude(vector<int>& gain) {
        int altitude = 0, best = 0;
        for (int delta : gain) {
            altitude += delta;
            best = max(best, altitude);
        }
        return best;
    }
};

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        altitude = 0
        best = 0
        for delta in gain:
            altitude += delta
            best = max(best, altitude)
        return best

/**
 * @param {number[]} gain
 * @return {number}
 */
var largestAltitude = function(gain) {
  let altitude = 0, best = 0;
  for (const delta of gain) {
    altitude += delta;
    if (altitude > best) best = altitude;
  }
  return best;
};