📌 点击直达笔试专栏 👉《大厂笔试突围》

💻 春秋招笔试突围在线OJ 笔试突围OJ](bishipass.com)

03. 山峰观测站数据分析

问题描述

LYA是一名地理数据分析师，负责分析山峰观测站收集的海拔高度数据。观测站在一条直线上设置了 $m$ 个测量点，按顺序测量得到了海拔高度序列。

LYA需要找出所有满足"山峰特征"的连续区间。一个区间具有山峰特征需要满足：

1. 区间内的海拔高度先呈现单调非递减趋势（即对于任意 $i\le j\le k$，有 $height[i]\le height[j]$）
2. 然后呈现单调非递增趋势（即对于任意 $k\le p\le q$，有 $height[p]\ge height[q]$）
3. 允许相邻测量点有相同的海拔高度

在所有满足山峰特征的区间中，LYA想要找到海拔高度最大值与最小值差值最大的区间，并返回这个最大差值。

输入格式

第一行包含一个正整数 $m$，表示测量点的数量。

第二行包含 $m$ 个非负整数，用空格分隔，表示各测量点的海拔高度。

输出格式

输出一个整数，表示所有山峰特征区间中海拔高度最大差值。

样例输入

8
1 2 3 5 4 4 8 1

5
15 15 15 15 15

6
3 8 12 10 6 9

样例输出

7

0

9

数据范围

• $1\le m\le 1000$
• $0\le height[i]\le 10^6$

样例	解释说明
样例1	存在区间[1,2,3,5,4,4]和[4,8,1]都满足山峰特征，其中[4,8,1]的差值最大为8-1=7
样例2	整个数组都满足山峰特征（所有值相等），海拔差值为15-15=0
样例3	区间[3,8,12,10,6]满足山峰特征，最大差值为12-3=9

题解

这道题的关键在于理解山峰特征的定义，然后高效地找出所有满足条件的区间。

核心思路：

与其枚举所有可能的区间（这样会超时），不如换个思路：将每个位置都当作可能的"山峰顶点"，然后向左右扩展找到最大的满足条件的区间。

算法步骤：

1. 预处理左边界： 对于每个位置 $i$，计算从 $i$ 向左能扩展到的最远位置 $left[i]$，使得这段区间满足单调非递减
2. 预处理右边界： 对于每个位置 $i$，计算从 $i$ 向右能扩展到的最远位置 $right[i]$，使得这段区间满足单调非递增
3. 计算答案： 对于每个位置 $i$ 作为峰顶，区间 $[left[i],right[i]]$ 就是一个满足条件的山峰区间
   • 区间的最大值就是 $height[i]$（峰顶）
   • 区间的最小值只能出现在两端，即 $\min (height[left[i]],height[right[i]])$
   • 差值为 $height[i]-\min (height[left[i]],height[right[i]])$

为什么这样是对的？

• 任何满足山峰特征的区间都必然有一个峰顶位置
• 通过预处理，我们能快速找到以任意位置为峰顶的最大山峰区间
• 这样可以保证不遗漏任何可能的区间，同时避免重复计算

时间复杂度： $O(m)$
空间复杂度： $O(m)$

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()# 读取输入数据
m = int(input())
if m == 0:print(0)exit()heights = list(map(int, input().split()))# 预处理每个位置向左的边界
left_bound = [0] * m
left_bound[0] = 0for i in range(1, m):if heights[i-1] <= heights[i]:  # 满足非递减条件left_bound[i] = left_bound[i-1]  # 继续向左扩展else:left_bound[i] = i  # 无法扩展，边界就是自己# 预处理每个位置向右的边界  
right_bound = [0] * m
right_bound[m-1] = m-1for i in range(m-2, -1, -1):if heights[i] >= heights[i+1]:  # 满足非递增条件right_bound[i] = right_bound[i+1]  # 继续向右扩展else:right_bound[i] = i  # 无法扩展，边界就是自己# 计算最大差值
max_diff = 0
for i in range(m):# 以位置i为峰顶的山峰区间peak_val = heights[i]  # 峰顶值（最大值）min_val = min(heights[left_bound[i]], heights[right_bound[i]])  # 最小值在两端curr_diff = peak_val - min_valmax_diff = max(max_diff, curr_diff)print(max_diff)

• Cpp

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(NULL);int m;cin >> m;if (m == 0) {cout << 0 << endl;return 0;}vector<int> h(m);  // 海拔高度数组for (int i = 0; i < m; i++) {cin >> h[i];}// 预处理左边界数组vector<int> left(m);left[0] = 0;for (int i = 1; i < m; i++) {if (h[i-1] <= h[i]) {left[i] = left[i-1];  // 向左扩展} else {left[i] = i;  // 边界为当前位置}}// 预处理右边界数组vector<int> right(m);right[m-1] = m-1;for (int i = m-2; i >= 0; i--) {if (h[i] >= h[i+1]) {right[i] = right[i+1];  // 向右扩展} else {right[i] = i;  // 边界为当前位置}}// 计算最大差值int result = 0;for (int i = 0; i < m; i++) {int peak = h[i];  // 峰顶高度int valley = min(h[left[i]], h[right[i]]);  // 两端最小值result = max(result, peak - valley);}cout << result << endl;return 0;
}

• Java

import java.util.*;
import java.io.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int m = Integer.parseInt(br.readLine());if (m == 0) {System.out.println(0);return;}String[] heightStrs = br.readLine().split(" ");int[] heights = new int[m];for (int i = 0; i < m; i++) {heights[i] = Integer.parseInt(heightStrs[i]);}// 计算每个位置的左边界int[] leftBound = new int[m];leftBound[0] = 0;for (int i = 1; i < m; i++) {if (heights[i-1] <= heights[i]) {leftBound[i] = leftBound[i-1];  // 继续向左扩展} else {leftBound[i] = i;  // 边界为当前位置}}// 计算每个位置的右边界int[] rightBound = new int[m];rightBound[m-1] = m-1;for (int i = m-2; i >= 0; i--) {if (heights[i] >= heights[i+1]) {rightBound[i] = rightBound[i+1];  // 继续向右扩展} else {rightBound[i] = i;  // 边界为当前位置}}// 计算最大差值int maxDiff = 0;for (int i = 0; i < m; i++) {int peakHeight = heights[i];  // 峰顶高度int minHeight = Math.min(heights[leftBound[i]], heights[rightBound[i]]);  // 两端最小值maxDiff = Math.max(maxDiff, peakHeight - minHeight);}System.out.println(maxDiff);}
}