华为7月23日机考真题

区间内的海拔高度先呈现单调非递减趋势（即对于任意 $i \leq j \leq k$ ，有 $h e i g h t [i] \leq h e i g h t [j]$ ）
然后呈现单调非递增趋势（即对于任意 $k \leq p \leq q$ ，有 $h e i g h t [p] \geq h e i g h t [q]$ ）
允许相邻测量点有相同的海拔高度

在所有满足山峰特征的区间中，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

样例输出

数据范围

$1 \leq m \leq 1000$
$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

题解

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

核心思路：

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

算法步骤：

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

为什么这样是对的？

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

时间复杂度：

(

)

O(m)

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

(

)

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)

#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;
    }
    
    vectorint> h(m);  // 海拔高度数组
    for (int i = 0; i  m; i++) {
        cin >> h[i];
    }
    
    // 预处理左边界数组
    vectorint> 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;  // 边界为当前位置
        }
    }
    
    // 预处理右边界数组
    vectorint> 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);
    }
}

文章来源于互联网:华为7月23日机考真题

相关推荐: spring通过Spring Integration实现tcp通信

1:Spring Integration TCP 核心概念 Spring Integration TCP 模块主要提供了以下组件：连接工厂 (ConnectionFactory): 负责创建和管理 TCP 连接…

华为7月23日机考真题

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

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

03. 山峰观测站数据分析

问题描述

输入格式

输出格式

样例输入

样例输出

数据范围

题解

参考代码

相关推荐

对比kimi、通义千问、文心一言的写代码能力

热门文章

AI大模型,我们的未来