Fast algorithm for linear context finding
You can solve this in $O(n \lg^2 n)$ time.

Build a (balanced) binary tree with $n$ nodes, where the leaves are annotated with the values $x_1,x_2,\dots,x_n$, and $x_i$ is placed on the $i$th leaf from the left.  Annotate each internal node $v$ in the tree with the maximum value over all the leaves in the subtree rooted at $v$.  For instance, the root is annotated with $\max(x_1,x_2,\dots,x_n)$.  The tree and the annotations can be built in $O(n)$ time.

Next, note that, for any $j,k$, a sequence $x_j, x_{j+1}, \dots, x_k$ of consecutive leaves can be covered by some union of $O(\lg n)$ subtrees.  In particular, given any $j,k$, we can compute $\max(x_j,x_{j+1},\dots,x_k)$ in $O(\lg n)$ time, by traversing the tree and using the annotations on the internal nodes at the top of those $O(\lg n)$ subtrees.

Now, to compute $y_k$, we do a binary search to find the largest $j$ such that $\max(x_j,x_{j+1},\dots,x_{k-1})&lt;x_k$ but $\max(x_{j-1},x_j,x_{j+1},\dots,x_{k-1})\ge x_k$.  Each iteration of the binary search takes $O(\lg n)$ time, and the binary search takes at most $O(\lg n)$ iterations, so this allows us to compute each $y_k$ in $O(\lg^2 n)$ time.

Finally, there are $n$ $y$-values that we want to compute, so the total running time is $O(n \lg^2 n)$.

This can be adjusted to work in an incremental/online/streaming fashion, with $O(\lg^2 n)$ running time per value of $x$ received, by tweaking the structure of the binary tree appropriately.



It's possible you might be able to get a slightly better solution by using 2-D range trees, where you store the $n$ points $(i,x_i)$ in the tree (for $i=1,2,\dots,n$).  However, I'm not certain.