問題: AtCoder ABC 235 B — Climbing Takahashi English · 한국어
各地点の高さは、進む順に並んでいます。高橋は最初の地点から出発し、次の地点の高さが現在の地点より厳密に高い場合にだけ進み続けます。初めて同じ高さまたは低い高さの地点に来たら、その地点には到着せずに止まります。求めるのは最後に到着した地点の高さです。
答えを最初の高さで初期化し、2番目の高さから順に調べます。高さが増加している間は答えを更新し、初めて増加しない高さを見つけたら走査を終了します。すべての高さが増加し続ける場合は最後の高さが答えになり、2番目の高さが同じか低い場合は最初の高さが答えのままです。
時間計算量はO(N)、高さ配列を保持する追加領域計算量はO(N)です。
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(input.readLine().trim());
int[] heights = new int[n];
StringTokenizer tokens = new StringTokenizer(input.readLine());
for (int i = 0; i < n; i++) {
heights[i] = Integer.parseInt(tokens.nextToken());
}
int answer = heights[0];
for (int i = 1; i < n; i++) {
if (heights[i] <= heights[i - 1]) {
break;
}
answer = heights[i];
}
System.out.println(answer);
}
}