[面经] Strava Coding：海拔采样中的第一段爬升（严格版 + 容忍小幅下降）

[面经] Strava Coding：海拔采样中的第一段爬升（严格版 + 容忍小幅下降）

朋友最近面了 Strava，分享了他技术电面里的一道题。给定一串按固定间隔采样的海拔，找第一段爬升的起止下标。题目给同一个函数加了一个开关，分两版：严格版里海拔不能下降；容忍版里允许短暂下降，但降幅不能超过目前已爬升高度的 20%，而且后面必须再涨过之前的最高点。代码不长，难的是下标语义，起点、终点、下降的判定方式都有坑。下面方法 A 是朋友在面试里写的做法，方法 B 是我们后来复盘时提出的另一种拆法。

## 题目

实现 `first_climb(elevations, tolerate_descent)`，返回第一段爬升的 `[start, end]`，没有爬升返回 `[]`。

- 起点：第一个严格上升位置的前一个采样点，即最小的 `s` 使 `elevations[s + 1] > elevations`。上升之前的平台段里同值的采样点不算。
- 终点：爬升过程中最终最高点 `P` 第一次到达的位置。之后同高度的平台不算，所以终点不一定是爬升的最后一个采样点。
- 严格版（`tolerate_descent = false`）：从起点出发，只要不下降就继续，遇到第一个下降就停。
- 容忍版（`tolerate_descent = true`）：某个采样点低于当前最高点 `P` 时进入下降段。下降段持续到第一个严格高于 `P` 的采样点为止（等于 `P` 不结束下降段，段内可以上下波动）。设 `gain = P - elevations[start]`，`m` 是下降段内的最低点，`loss = P - m`。下降被容忍当且仅当：后面确实出现了高于 `P` 的采样点，并且 `5 * loss <= gain`（用整数精确判断）。容忍后从新的最高点继续，后面的下降用更新后的 `P` 和 `gain` 同样判断；不容忍则爬升结束于 `P` 第一次到达的位置。

约束：`elevations` 长度最大 1e5，海拔在 -1e5 到 1e5 之间。

## 例题走一遍

`elevations = [5, 5, 6, 10, 20, 25, 24, 26, 30, 28]`，容忍版：

1. 起点是下标 1：5 → 6 是第一次上升。下标 0 也是 5，但它不在这次上升的前一位，不算。
2. 一路上行到 25（下标 5）。此时 `P = 25`，`gain = 25 - 5 = 20`。
3. 下标 6 是 24，低于 `P`，进入下降。下标 7 是 26，严格高于 `P`，下降段结束：`loss = 25 - 24 = 1`，`5 * 1 = 5 <= 20`，容忍。`P` 更新为 26（下标 7）。
4. 下标 8 是 30，`P = 30`。
5. 下标 9 是 28，进入下降，但后面没有采样点了，永远涨不回 30 以上，不容忍。爬升结束于 30 第一次到达的下标 8。

输出 `[1, 8]`。严格版在第 3 步就停了（24 < 25），输出 `[1, 5]`。

## 核心思路

两个要点决定了整个实现：

- 终点只由"最终最高点第一次到达的位置"决定。也就是说全程只需维护 `P` 和它的位置，上行、平台、被容忍的下降都不直接产生答案，只在更新 `P` 时更新终点候选。
- 容忍版里下降必须整段判断。下降段的最低点可能出现在海拔回到恰好 `P` 之后，因为等于 `P` 不结束下降段。如果一回到 `P` 就结算 `loss`，会把后面的更低点漏掉。

## 方法 A：单次扫描 + 状态机（朋友的做法）

朋友的做法是一遍扫完，用一个标志位区分当前在爬升段还是下降段。爬升段里更新 `P` 和它的位置；进入下降段后只记录段内最低点，等第一个高于 `P` 的采样点出现时再整段结算。扫到结尾时如果还在下降段里，这个下降天然不被容忍（没有高于 `P` 的采样点），直接用当前终点候选作答。

```python
def first_climb(elevations, tolerate_descent):
    e = elevations
    n = len(e)

    # 起点：第一次严格上升的前一个采样点
    s = -1
    for i in range(n - 1):
        if e[i + 1] > e[i]:
            s = i
            break
    if s == -1:
        return []

    peak = e        # P：目前为止的最高点
    peak_idx = s       # P 第一次到达的位置
    in_descent = False
    descent_min = None  # 当前下降段内的最低点

    for i in range(s + 1, n):
        v = e[i]
        if not in_descent:
            if v >= peak:
                if v > peak:
                    peak, peak_idx = v, i
                # 与 P 持平：peak_idx 不动，终点取第一次到达
            elif not tolerate_descent:
                break  # 严格版：第一次下降就结束
            else:
                in_descent = True
                descent_min = v
        else:
            if v > peak:
                # 下降段结束，整段结算
                gain = peak - e
                loss = peak - descent_min
                if 5 * loss <= gain:
                    peak, peak_idx = v, i
                    in_descent = False
                    descent_min = None
                else:
                    break  # 不容忍：结束于旧 P 的位置
            elif v < descent_min:
                descent_min = v
            # v == peak 时下降段继续，最低点可能还在后面

    return [s, peak_idx]
```

## 方法 B：严格爬升分段 + 下降前瞻（我们提出的另一种解法）

复盘时我们提出把过程拆成一段一段：先用严格规则把当前段推到顶，遇到下降就暂停，用一段前瞻把整个下降段扫完（找最低点和第一个高于 `P` 的位置），整段结算一次。容忍就从新高点重复这个过程，不容忍就结束。和方法 A 的区别是控制流：A 是逐个采样点的状态机，B 是"爬升段 / 下降段"交替的块结构，判定逻辑集中在下降段的结算里，写的时候不容易漏掉"等于 `P` 不结束下降段"这类细节。每个下标只被爬升段或下降段扫到常数次，总复杂度不变。

```python
def first_climb(elevations, tolerate_descent):
    e = elevations
    n = len(e)

    s = -1
    for i in range(n - 1):
        if e[i + 1] > e[i]:
            s = i
            break
    if s == -1:
        return []

    peak = e
    peak_idx = s
    i = s  # 当前位置；不在下降段里时 e[i] == peak

    while True:
        # 1) 严格延伸：不下降就一直走
        while i + 1 < n and e[i + 1] >= e[i]:
            i += 1
            if e[i] > peak:
                peak, peak_idx = e[i], i
        if i + 1 >= n:
            return [s, peak_idx]  # 爬升中走到了结尾

        # e[i + 1] < e[i] == peak：出现低于最高点的采样点
        if not tolerate_descent:
            return [s, peak_idx]

        # 2) 下降前瞻：扫完整个下降段
        descent_min = e[i + 1]
        j = i + 1
        while j < n and e[j] <= peak:
            if e[j] < descent_min:
                descent_min = e[j]
            j += 1
        if j >= n:
            return [s, peak_idx]  # 之后再没高过 peak

        gain = peak - e
        loss = peak - descent_min
        if 5 * loss > gain:
            return [s, peak_idx]  # 降得太深，爬升结束

        # 容忍：从新高点继续
        peak, peak_idx = e[j], j
        i = j
```

## 复杂度

- 时间：O(n)。A 扫一遍；B 里每个下标只被爬升段或下降段覆盖常数次。
- 空间：O(1)，只存几个标量。

## 易错点

1. 起点是第一次上升的前一位，不是最开始的最低点。例 1 里 `[3, 2, 1, 0, 0, 1, ...]` 的起点是下标 4 不是 3：下标 3 的 0 不在 0 → 1 这次上升的前一位。
2. 终点取最终最高点第一次到达的位置，峰顶后面的平台段不算。`[0, 10, 8, 11, 11, 9, 10]` 的终点是下标 3 不是 4。
3. 下降段的结束条件是严格大于 `P`。回到恰好 `P` 不算结束，最低点可能出现在那之后。`[0, 10, 5, 10, 4, 12]` 里决定结果的是后面的 4，不是先出现的 5。
4. 20% 用整数判断 `5 * loss <= gain`，不要用浮点百分比，也不能写成 `<`：`loss` 恰好等于 20% 是允许的（`[0, 10, 8, 11]`，`5 * 2 = 10 <= 10`）。
5. `gain` 每次结算都用当前的 `P` 减去起点的海拔。爬得越高，后续下降的容忍额度越大，不要拿第一段的 `gain` 用到底。

验证：页面上的三个例子（含两个版本的输出）都对过，另外构造了边界用例（恰好 20%、回到 P 后再创新低、连续两次被容忍的下降、负海拔、以下降结尾等），再用 3000 组随机序列对拍两种方法，结果全部一致。

觉得有帮助的话欢迎收藏、加米。也欢迎讨论变体，比如把 20% 换成参数，或者返回所有爬升段。