The Himalayas (ZOJ)：統計山峰數量

題目描述

給定 N (≤ 50) 個採樣高度 H[i]，相鄰高度互不相等。定義峰值：2 ≤ i ≤ N-1 且 H[i-1] < H[i] > H[i+1]。統計峰值個數。

算法：單次掃描

#include 

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int N; scanf("%d", &N);
        int h[55];
        for (int i=0; i h[i+1]) ++peaks;
        }
        printf("%d\n", peaks);
    }
}

複雜度

• 時間：O(N) 每測試用例
• 空間：O(N) 存儲高度數組

樣例

輸入：
2
9
1 3 2 4 6 3 2 3 1
5
1 2 3 4 5

輸出：
3
0

第一組峰值位置：3 (i=1)、6 (i=4)、3 (i=7)。