题解 | 山脉突起度分析

package main

import (
	"fmt"
)

func max(a,b int ) int {
    if a >b {
        return a
    }
    return b
}

func main() {
	var n int
	fmt.Scanf("%d", &n)
	var k = make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scanf("%d", &k[i])
	}
    var hasUp bool = true // 是否非减, 默认起始位置都是升坡
    var maxH,l,top, r int = 0,0,0,0 // 最大突起度，单个山脉的左边缘、顶部、右边缘
    for i := 1;i<n ;i++{
        if k[i] >= k[i-1] && hasUp {
            continue // 仍在上坡
        }
        if k[i] > k[i-1] && !hasUp { // 遍历了一个山脉，但没有考虑到最后是下坡的情况
            r = i -1
            t := max(k[top] - k[l], k[top] - k[r])
            if t > maxH {
                maxH = t
            }
            l = i-1
            hasUp = true
            continue
        }
        if k[i] < k[i-1] && hasUp {
            // i-1是坡顶
            top = i -1
            hasUp = false
            continue
        }
        if k[i] <= k[i-1] && !hasUp {
            continue // 仍在下坡
        }
    }
    // 考虑最后是下坡的情况
    if n > 1 {
        r = n-1
        t := max(k[top] - k[l], k[top] - k[r])
        if t > maxH {
            maxH = t
        }
    }
    fmt.Println(maxH)
}