山脉突起度分析_牛客题霸

一支地质勘探队正在对一个新发现的星球进行地形扫描。他们沿着一条直线收集了一系列离散的海拔数据点，形成了一个地形剖面。现在，你需要帮助他们分析这些数据，以找出最显著的山脉结构。在地质学中，我们关心的是一个山峰相对于其周围地形的“突起度”（Prominence），这可以衡量一座山脉的独立性和显著性。给定一个由非负整数组成的数组，表示个连续采样点的海拔高度。我们需要从这个地形剖面中识别出所有符合特定条件的“山脉区间” （其中）。一个区间被定义为“山脉区间”，当且仅当存在一个“峰顶”索引（），使得该区间的海拔变化满足以下两个连续的趋势： 1. **上升坡段**：从区间的起点到峰顶的地形是单调非递减的。即，对于任意满足的索引，都有。 2. **下降坡段**：从峰顶到区间的终点的地形是单调非递增的。即，对于任意满足的索引，都有。注意，一个有效的“山脉区间”必须同时包含严格的上升和下降部分，即。对于每一个有效的“山脉区间”，其**突起度** 被定义为该区间的海拔最高点（即峰顶）与该区间的海拔最低点之间的差值。区间的最低点必然位于其两个端点之一，即。因此，突起度计算公式为。你的任务是，在所有可能的“山脉区间”中，找到最大的那个**突起度**。

输入描述:

- 第一行：一个整数 ，代表地形剖面中的数据点数量。- 第二行： 个以空格分隔的非负整数，代表各点的海拔高度。- 数组长度 满足 - 每个元素的海拔高度 满足

输出描述:

一个整数，表示所有“山脉区间”中最大的突起度。

示例1

输入

8
1 2 3 5 4 4 8 1

输出

说明

存在两个山脉区间：
1.  区间 （数值为 `1 2 3 5 4 4`），峰顶在索引 4（值为 5）。最低点为 。
-   突起度 。
2.  区间 （数值为 `4 4 8 1`），峰顶在索引 7（值为 8）。最低点为 。
-   突起度 。

比较所有区间的突起度，最大值为 。

示例2

输入

5
15 15 15 15 15

输出

说明

虽然整个区间 `[15 15 15 15 15]` 既是单调非递减又是单调非递增，但它没有一个严格的峰顶（即不存在  的结构）。因此，不存在任何有效的“山脉区间”，最大突起度为 。

示例3

输入

6
3 8 12 10 6 9

输出

说明

唯一有效的山脉区间是 （数值为 `3 8 12 10 6`）。
-   峰顶为 。
-   区间端点为  和 。
-   突起度 。
这是唯一有效的山脉区间，因此最大突起度为 。

备注:

本题由牛友@Charles 整理上传