Kickstart2020 RoundB: Bike Tour

https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc8/00000000002d82e6

問題

各要素が山の高さ（i番目の要素は$H_i$とする）であるN個のチェックポイントが与えられたとき、ピークとなる$H_i$の数をカウントする。ピークとなる条件は、

• 最初、またはN番目の要素ではない
• 一つ前と一つ後の高さよりも高い

実装

2番目の要素からN-1番目の要素について、上記の二つ目の条件をチェックすれば良い。このときの条件チェックは、配列要素の比較でO(1)で実行でき、トータルの計算量はO(N)。

T = int(input())
for t in range(1, T + 1):
    N = int(input())
    ckpts = list(map(int, input().split()))
    res = 0
    for i in range(1, N - 1):
        if ckpts[i - 1] < ckpts[i] and ckpts[i] > ckpts[i + 1]:
            res += 1
    print('Case #{}: {}'.format(t, res))