Find all $k$ local maximums in an array of length $n$ in $O(n \log k)$ time
Hint: Use some data structure that allows insertion, deletion, and search in logarithmic time to maintain a snapshot of the $k$ preceding elements, and use it to determine whether the next element is a $k$-maximum in time $O(\log k)$.