思路

设 $f_i$ 为到达第 $i$ 座楼的最少跳跃次数。相邻楼之间总能跳跃，所以 $f_i\le f_{i-1}+1$。

对固定终点 $i$，若一次跳跃从某个更早位置 $j$ 到达 $i$，中间楼要么全部低于两端，要么全部高于两端。沿下标从左到右扫描时，可能成为前一种跳跃起点的位置会按高度形成一个单调序列；后一种跳跃同理形成方向相反的单调序列。

做法

维护两个存放下标的单调栈。一个栈的高度单调不增，用来处理“中间全部更低”的跳跃；另一个栈的高度单调不减，用来处理“中间全部更高”的跳跃。

处理位置 $i$ 时，先令 $f_i=f_{i-1}+1$。对于第一个栈，不断弹出高度小于 $h_i$ 的栈顶，每个被弹出的下标都能直接跳到 $i$，用它更新 $f_i$；弹出结束后，若栈非空，当前栈顶也能作为候选起点。若栈顶与 $h_i$ 相等，删除旧的等高位置，只保留更新的下标。第二个栈对大于关系做完全对称的处理。

正确性证明

考虑任意合法跳跃 $j\to i$。若中间所有楼都低于两端，则从 $j$ 到 $i$ 的扫描过程中，不会存在一个高度不低于两端较小值的位置挡在两者之间。因此在处理 $i$ 时，$j$ 要么作为较低元素被第一个单调栈弹出，要么成为弹出结束后的栈顶，算法会检查它。若中间所有楼都高于两端，对称地，第二个单调栈会检查 $j$。

反过来，单调栈弹出的元素与弹出结束后的栈顶，按照栈维护的不变量，其间不存在破坏对应严格高低关系的位置，因此算法采用的转移都对应合法跳跃。算法检查了到达每个位置的全部必要候选转移，并取最小值，所以得到的 $f_n$ 是最少跳跃次数。

复杂度

每个下标在每个单调栈中至多入栈、出栈各一次，时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。