题解 | #山脉突起度分析#

题目链接

题目描述

给定一个由非负整数组成的海拔数组 $E$ 。一个“山脉区间” $[i, j]$ 被定义为存在一个峰顶索引 $m$ ( $i \le m \le j$ )，使得 $E[i \dots m]$ 单调非递减，且 $E[m \dots j]$ 单调非递增。

一个有效的山脉区间必须包含严格的上升和下降部分，这由条件 $i < m$ 且 $m < j$ 来保证。

每个有效山脉区间的“突起度” $P$ 定义为峰顶海拔与区间两端点海拔较低者的差值： $P = E_m - \min(E_i, E_j)$ 。

任务是找到所有可能的“山脉区间”中，最大的那个“突起度”。

输入:

第一行：数据点数量 $N$ 。
第二行： $N$ 个海拔高度 $E_i$ 。

输出:

一个整数，代表最大的突起度。若不存在有效的山脉区间，则为 $0$ 。

解题思路

这是一个寻找最优子结构的问题。暴力枚举所有可能的区间起点 $i$ 、终点 $j$ 和峰顶 $m$ 的时间复杂度为 $\mathcal{O}(N^3)$ ，无法接受。一个稍好的方法是枚举每个点作为峰顶，然后向两边扩展，时间复杂度为 $\mathcal{O}(N^2)$ ，仍然过高。

我们可以通过动态规划的思想，利用两次线性扫描来预先计算必要的信息，从而在 $\mathcal{O}(N)$ 的时间内解决问题。

核心思想

核心思想是，对于数组中的每一个点 $E_m$ ，我们都将它视为一个潜在的峰顶。然后，我们快速地找出以它为峰顶的、尽可能延伸的最长山脉区间的左右边界 $[i, j]$ 。

预计算

为了能够快速找到边界，我们需要两个辅助数组：

$L$ 数组： $L[m]$ 存储以索引 $m$ 为终点的单调非递减区间的起始索引。
$R$ 数组： $R[m]$ 存储以索引 $m$ 为起点的单调非递增区间的终止索引。

这两个数组可以通过一次正向和一次反向的线性扫描来计算：

计算 $L$ 数组（正向扫描）：从左到右遍历数组。对于当前点 $m$ ，如果 $E_{m-1} \le E_m$ ，说明非递减趋势得以延续，因此 $L[m]$ 应该继承前一个点的起始索引，即 $L[m] = L[m-1]$ 。否则，非递减趋势中断，一个新的非递减区间从当前点 $m$ 开始，即 $L[m] = m$ 。
计算 $R$ 数组（反向扫描）：从右到左遍历数组。对于当前点 $m$ ，如果 $E_{m+1} \le E_m$ ，说明非递增趋势得以延续，因此 $R[m]$ 应该继承后一个点的终止索引，即 $R[m] = R[m+1]$ 。否则，趋势中断，一个新的非递增区间从当前点 $m$ 开始，即 $R[m] = m$ 。

计算最大突起度

在预计算完 $L$ 和 $R$ 数组之后，我们进行第三次线性扫描：

遍历每一个索引 $m$ (从 $0$ 到 $N-1$ ) 作为潜在的峰顶。
对于每个 $m$ ，其构成的最长山脉区间的左边界是 $i = L[m]$ ，右边界是 $j = R[m]$ 。
根据题意，我们需要检查这是否是一个有效的山脉区间，即必须同时包含上升和下降坡段。这个条件可以简单地通过检查 $i < m$ 且 $m < j$ 来判断。
如果条件满足，我们就计算其突起度 $P = E_m - \min(E_i, E_j)$ ，并用它来更新我们记录的最大突起度。

整个算法包含三次独立的线性扫描，因此总时间复杂度为 $\mathcal{O}(N)$ 。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> E(n);
    for (int i = 0; i < n; ++i) {
        cin >> E[i];
    }

    if (n < 3) {
        cout << 0 << endl;
        return 0;
    }

    vector<int> L(n);
    L[0] = 0;
    for (int i = 1; i < n; ++i) {
        if (E[i - 1] <= E[i]) {
            L[i] = L[i - 1];
        } else {
            L[i] = i;
        }
    }

    vector<int> R(n);
    R[n - 1] = n - 1;
    for (int i = n - 2; i >= 0; --i) {
        if (E[i + 1] <= E[i]) {
            R[i] = R[i + 1];
        } else {
            R[i] = i;
        }
    }

    int max_prominence = 0;
    for (int m = 0; m < n; ++m) {
        int i = L[m];
        int j = R[m];

        // 必须有严格的上升和下降段
        if (i < m && m < j) {
            int prominence = E[m] - min(E[i], E[j]);
            max_prominence = max(max_prominence, prominence);
        }
    }

    cout << max_prominence << endl;

    return 0;
}

import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] E = new int[n];
        for (int i = 0; i < n; i++) {
            E[i] = sc.nextInt();
        }

        if (n < 3) {
            System.out.println(0);
            return;
        }

        int[] L = new int[n];
        L[0] = 0;
        for (int i = 1; i < n; i++) {
            if (E[i - 1] <= E[i]) {
                L[i] = L[i - 1];
            } else {
                L[i] = i;
            }
        }

        int[] R = new int[n];
        R[n - 1] = n - 1;
        for (int i = n - 2; i >= 0; i--) {
            if (E[i + 1] <= E[i]) {
                R[i] = R[i + 1];
            } else {
                R[i] = i;
            }
        }

        int max_prominence = 0;
        for (int m = 0; m < n; m++) {
            int i = L[m];
            int j = R[m];

            // 必须有严格的上升和下降段
            if (i < m && m < j) {
                int prominence = E[m] - Math.min(E[i], E[j]);
                max_prominence = Math.max(max_prominence, prominence);
            }
        }

        System.out.println(max_prominence);
    }
}

# 读取输入
n = int(input())
if(n==0):
    E=[]
else:
    E = list(map(int, input().split()))

if n < 3:
    print(0)
else:
    # L[m] = 起始索引 of a non-decreasing slope ending at m
    L = [0] * n
    for i in range(1, n):
        if E[i - 1] <= E[i]:
            L[i] = L[i - 1]
        else:
            L[i] = i
            
    # R[m] = 终止索引 of a non-increasing slope starting at m
    R = [0] * n
    R[n - 1] = n - 1
    for i in range(n - 2, -1, -1):
        if E[i + 1] <= E[i]:
            R[i] = R[i + 1]
        else:
            R[i] = i
            
    max_prominence = 0
    for m in range(n):
        i = L[m]
        j = R[m]
        
        # 必须有严格的上升和下降段
        if i < m < j:
            prominence = E[m] - min(E[i], E[j])
            max_prominence = max(max_prominence, prominence)
            
    print(max_prominence)

算法及复杂度

算法：动态规划（预计算）
时间复杂度： $\mathcal{O}(N)$ ，算法主要包含三次独立的线性扫描（计算 $L$ 数组，计算 $R$ 数组，以及最终遍历计算突起度），每次扫描的时间复杂度都是 $\mathcal{O}(N)$ 。
空间复杂度： $\mathcal{O}(N)$ ，用于存储 $L$ 和 $R$ 两个辅助数组。