📌 點擊直達筆試專欄 👉《大廠筆試突圍》

💻 春秋招筆試突圍在線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);}
}