求数组任意元素右边第 $k$ 个比它小的元素
问题引入我们都知道，如果我们想求得一个数组任意元素左边或右边的第一个比他大或小的元素，可以通过单调栈实现，时间和空间复杂度都是 $O(n)$ 。但是如果我们想求得一个数组任意元素左边或右边的第 $k$ 个比他大或小的元素，该怎么办呢？
解决思路线段树 + 二分（线段树上二分优化）我们考虑使用线段树来解决这个问题。我们可以用线段树来维护区间最小值，然后通过二分查找来找到第 $i$ 个比他小或大的元素的位置，共 $k$ 次二分查找，时间复杂度为 $O(nk\log^2 n)$ 。
考虑线段树上二分优化，可以消去一层二分，时间复杂度为 $O(nk\log n)$ 。
这样，我们就得到了时间复杂度为 $O(nk\log n)$ 的解法。
但是这种解法显然不够优秀。不论从实现复杂性上看，还是从复杂度上看都不够好。
时间上，我们带有一个 $\log n$ ，而空间上，我们需要四倍的空间来维护线段树。
再加上线段树的常数较大，这显然不是一个好的解法。
单调栈 + 动态规划回顾考虑再次回到我们一开始的思路，我们可以通过单调栈 + 动态规划来解决这个问题。
让我们先考虑如何求得一个数组任意元素右边的第一 ...
Hello World!
Hello World!