解説

まず、移動パターンは4通りしかありません。

$h _ {i}$ $\le$ $h _ {j}$ かつ $\max(h _ {i+ 1} \cdots h _ {j - 1})$ < $\min(h _ {i}, h _ {j})$ → $i$ 番目から一番近い $h _ {i}$ 以上のところに行く

$h _ {i}$ $\ge$ $h _ {j}$ かつ $\max(h _ {i+ 1} \cdots h _ {j - 1})$ < $\min(h _ {i}, h _ {j})$ → $j$ 番目に一番近い $h _ {j}$ 以上のところからくる

$h _ {i}$ $\ge$ $h _ {j}$ かつ $\min(h _ {i+ 1} \cdots h _ {j - 1})$ < $\max(h _ {i}, h _ {j})$ → $i$ 番目から一番近い $h _ {i}$ 以下のところに行く

$h _ {i}$ $\le$ $h _ {j}$ かつ $\min(h _ {i+ 1} \cdots h _ {j - 1})$ < $\max(h _ {i}, h _ {j})$ → $j$ 番目に一番近い $h _ {j}$ 以下のところからくる

なので、各位置においてどこからくるかとどこにいくかは、stackを用いて全体で $O(n)$ で求めることができます。

あとは左から右にしか行かないのでDPでよくて、全体の計算量は $O(n)$ です

提出コード