网站开发需要干什么,网站管理平台模板,建个私人网站怎么做,wordpress后台登录logo#x1f4cc; 点击直达笔试专栏 #x1f449;《大厂笔试突围》
#x1f4bb; 春秋招笔试突围在线OJ 笔试突围OJ](bishipass.com)
03. 山峰观测站数据分析
问题描述
LYA是一名地理数据分析师#xff0c;负责分析山峰观测站收集的海拔高度数据。观测站在一条直线上设置了… 点击直达笔试专栏 《大厂笔试突围》 春秋招笔试突围在线OJ 笔试突围OJ](bishipass.com)
03. 山峰观测站数据分析
问题描述
LYA是一名地理数据分析师负责分析山峰观测站收集的海拔高度数据。观测站在一条直线上设置了 mmm 个测量点按顺序测量得到了海拔高度序列。
LYA需要找出所有满足山峰特征的连续区间。一个区间具有山峰特征需要满足
区间内的海拔高度先呈现单调非递减趋势即对于任意 i≤j≤ki \leq j \leq ki≤j≤k有 height[i]≤height[j]height[i] \leq height[j]height[i]≤height[j]然后呈现单调非递增趋势即对于任意 k≤p≤qk \leq p \leq qk≤p≤q有 height[p]≥height[q]height[p] \geq height[q]height[p]≥height[q]允许相邻测量点有相同的海拔高度
在所有满足山峰特征的区间中LYA想要找到海拔高度最大值与最小值差值最大的区间并返回这个最大差值。
输入格式
第一行包含一个正整数 mmm表示测量点的数量。
第二行包含 mmm 个非负整数用空格分隔表示各测量点的海拔高度。
输出格式
输出一个整数表示所有山峰特征区间中海拔高度最大差值。
样例输入
8
1 2 3 5 4 4 8 15
15 15 15 15 156
3 8 12 10 6 9样例输出
709数据范围
1≤m≤10001 \leq m \leq 10001≤m≤10000≤height[i]≤1060 \leq height[i] \leq 10^60≤height[i]≤106
样例解释说明样例1存在区间[1,2,3,5,4,4]和[4,8,1]都满足山峰特征其中[4,8,1]的差值最大为8-17样例2整个数组都满足山峰特征所有值相等海拔差值为15-150样例3区间[3,8,12,10,6]满足山峰特征最大差值为12-39
题解
这道题的关键在于理解山峰特征的定义然后高效地找出所有满足条件的区间。
核心思路
与其枚举所有可能的区间这样会超时不如换个思路将每个位置都当作可能的山峰顶点然后向左右扩展找到最大的满足条件的区间。
算法步骤
预处理左边界 对于每个位置 iii计算从 iii 向左能扩展到的最远位置 left[i]left[i]left[i]使得这段区间满足单调非递减预处理右边界 对于每个位置 iii计算从 iii 向右能扩展到的最远位置 right[i]right[i]right[i]使得这段区间满足单调非递增计算答案 对于每个位置 iii 作为峰顶区间 [left[i],right[i]][left[i], right[i]][left[i],right[i]] 就是一个满足条件的山峰区间 区间的最大值就是 height[i]height[i]height[i]峰顶区间的最小值只能出现在两端即 min(height[left[i]],height[right[i]])\min(height[left[i]], height[right[i]])min(height[left[i]],height[right[i]])差值为 height[i]−min(height[left[i]],height[right[i]])height[i] - \min(height[left[i]], height[right[i]])height[i]−min(height[left[i]],height[right[i]])
为什么这样是对的
任何满足山峰特征的区间都必然有一个峰顶位置通过预处理我们能快速找到以任意位置为峰顶的最大山峰区间这样可以保证不遗漏任何可能的区间同时避免重复计算
时间复杂度 O(m)O(m)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] 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[i1]: # 满足非递增条件right_bound[i] right_bound[i1] # 继续向右扩展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;}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[i1]) {right[i] right[i1]; // 向右扩展} 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[i1]) {rightBound[i] rightBound[i1]; // 继续向右扩展} 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);}
}
