华为7月23日机考真题

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

💻 春秋招笔试突围在线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$ 个非负整数，用空格分隔，表示各测量点的海拔高度。

输出格式

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

样例输入

81 2 3 5 4 4 8 1

515 15 15 15 15

63 8 12 10 6 9

样例输出

7

0

9

数据范围

• $1\le m\le 1000$
• 0 ≤ h e i g h t [ i ] ≤ 1 0 6 0 \\leq height[i] \\leq 10^6 0≤height[i]≤106

样例 解释说明 样例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 sysinput = lambda: sys.stdin.readline().strip()# 读取输入数据m = int(input())if m == 0: print(0) exit()heights = list(map(int, input().split()))# 预处理每个位置向左的边界left_bound = [0] * mleft_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] * mright_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 = 0for 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_val max_diff = max(max_diff, curr_diff)print(max_diff)

• Cpp

#include 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); }}