华为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$ 个非负整数，用空格分隔，表示各测量点的海拔高度。

输出格式

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

样例输入

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. 预处理左边界： 对于每个位置 $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] = 0

for 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-1

for 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_val
    max_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);
    }
}