题目描述

给定一个整数数组$array$，代表一系列时间点上的信号强度值。请在这些时间点中找出一个波峰区间 $[i, j]$（其中$i \le j$），满足以下两个连续阶段：

1. 区间前半段是单调非递减（即对于$i \le k < s \le m$，有$array[k] \le array[s]$）
2. 区间后半段是单调非递增（即对于$m \le n < o \le j$，有$array[n] \ge array[o]$）

必须同时出现两个阶段才能构成一个合法的波峰区间！

找出所有合法波峰区间中，最大值与最小值的差值最大的那个区间，返回这个最大差值。

思路概括

1. 枚举每个下标作为波峰的中心点（即峰顶位置$mid$
2. 向左扩展，找出最长的单调非递减段 $[L, mid]$
3. 向右扩展，找出最长的单调非递增段 $[mid, R]$
4. 判断是否$L < mid$ 且 $R > mid$，只有满足才构成一个合法波峰
5. 记录该波峰区间的最大值（峰值）和最小值（两端点中较小的），更新最大差值

问题本质分析

本题实质为枚举“山峰结构”的问题，要求找到一个先上升再下降的区间，并在所有这样的结构中找出最大高低差值。需要注意的是，必须先升再降，不能只有单调一段。使用双指针扩展判断每个点作为峰顶能延伸出的最长波峰段，最后取最大值。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int m;
    cin >> m;
    vector<int> array(m);
    for (int i = 0; i < m; i++) {
        cin >> array[i];
    }

    int ans = 0;
    for (int mid = 0; mid < m; mid++) {
        int L = mid, R = mid;

        // 向左扩展单调非递减段
        while (L > 0 && array[L - 1] <= array[L]) {
            L--;
        }

        // 向右扩展单调非递增段
        while (R + 1 < m && array[R] >= array[R + 1]) {
            R++;
        }

        // 必须左边实际扩展过且右边也扩展过，才是合法波峰
        if (L < mid && R > mid) {
            int peak = array[mid];
            int low = min(array[L], array[R]);
            ans = max(ans, peak - low);
        }
    }

    cout << ans << endl;
    return 0;
}

Python

def max_peak_diff(array):
    n = len(array)
    ans = 0

    for mid in range(n):
        L = mid
        while L > 0 and array[L - 1] <= array[L]:
            L -= 1

        R = mid
        while R + 1 < n and array[R] >= array[R + 1]:
            R += 1

        # 必须两边都扩展了，才是合法波峰
        if L < mid and R > mid:
            peak = array[mid]
            low = min(array[L], array[R])
            ans = max(ans, peak - low)

    return ans

if __name__ == "__main__":
    m = int(input())
    array = list(map(int, input().split()))
    print(max_peak_diff(array))

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int[] array = new int[m];
        for (int i = 0; i < m; i++) {
            array[i] = sc.nextInt();
        }

        System.out.println(maxPeakDiff(array));
        sc.close();
    }

    // 计算最大波峰区间差值
    public static int maxPeakDiff(int[] array) {
        int n = array.length;
        int ans = 0;

        for (int mid = 0; mid < n; mid++) {
            int L = mid;
            // 向左扩展单调非递减段
            while (L > 0 && array[L - 1] <= array[L]) {
                L--;
            }

            int R = mid;
            // 向右扩展单调非递增段
            while (R + 1 < n && array[R] >= array[R + 1]) {
                R++;
            }

            // 必须左右两边都扩展过才是合法波峰
            if (L < mid && R > mid) {
                int peak = array[mid];
                int low = Math.min(array[L], array[R]);
                ans = Math.max(ans, peak - low);
            }
        }

        return ans;
    }
}

题目内容

给定一个整数数组 $array$ ，代表在一系列连续时间点上检测到的信号强度值。我们需要在这一系列时间点中找出一个区间 $[i,j]$ (其中 $i<=j$ )，满足以下条件：

1.区间内的信号强度值先呈现单调非递減趋势(即对于 $i<= k<s<= m$，有 $array[k] <= array[s]$)

2.紧接着呈现单调非递增趋势(即对于 $m<=n<o<=j$，有 $array[n]>= aray[o]$)

3.这里的单调非递减和非递增趋势允许存在相等的相邻值。

在满足上述条件的区间叫做“波峰区间"，在所有的“波峰区间“中，找到信号强度最大值与最小值差值最大的那个区间，并返回这个最大差值。

$0<=array.length<=1000$

$array[i] ≥ 0$

输入描述

第一行输入一个数字 $m$ ，代表要输入的数组 $array$ 内的数字数量。

第二行输入 $m$ 个数字，数字用空格隔开。

输出描述

输出最大差值

样例1

输入

8
1 2 3 5 4 4 8 1

输出

7

说明

$[1,2,3,5,4,4]$ 是一个满足条件的区间，最大值是 $5$ ，最小值是 $1$ ，最大差值是 $4$ 。

$[4.8,1]$ 是第二个满足条件的区间，最大值是 $8$，最小值是 $1$ ，最大差值是 $7$ 。两个区间比较，最终最大差值是 $7$

样例2

输入

5
15 15 15 15 15

输出

0

说明

整个数组都满足先单调非递减后单调非递增的条件(因为所有值相等)。信号强度的最大值和最小值都是 $15$ ，差值为 $15-15=0$ 。

样例3

输入

6
3 8 12 10 6 9

输出

9

说明

满足条件的区间为 $[3,8,12,10,6]$ ，在此区间内，$[3,8,12]$ 单调非递减，$[12,10,6]$ 单调非递增。信号强度的最大值为 $12$ ，最小值为 $3$ ，差值为 $12-3=9$ ，这是所有满足条件区间中的最大差值。