浅 谈 二 维 单 调 栈

· · 算法·理论

引入

问题1

如何在一个单调的序列中查询第一个比 k 大的数？

学过OI的都知道直接二分一下即可，非常弱智，复杂度 O(\log N)。

问题2

如何在一个序列（不一定单调！）中查询第一个比k大的数？

我们先来看下面这个序列。
1 3 2 6 3 5 7
这个鬼东西貌似不怎么符合单调性，也就是我们不能二分。
难道只能打 O(N) 的暴力？
这不现实，查询多了必然会 TLE（悲。 有一个办法，既然它不单调……

那我们就让它单调！
我们考虑如果有一个数 j，它在 i 后面，但还比 i 小（或等于）。
它必然选不到。
因为如果 k 比 i 大，i 都不能满足它，小得可怜的 j 更不能满足。
如果 k 比 i 小，既然 i 在前面，那肯定选 i 而不是 j。
因此，如果有数比前面的数小（或等于），那它有没有都一样，删掉它不会影响答案。
也就是说，我们可以把原序列中递减的部分全部剔除，让小的数统统滚蛋。
上面的序列也就可以转化成这样：
1 3 6 7
既然它已经单调了，我们就可以愉快地跑二分了（喜。
具体实现可以维护一个单调栈，从后往前加数，如果栈顶小于这个数就 pop，最后把这个数放进去。
预处理 O(N)，查询 O(\log N)。

正片开始

问题三

如何在一个序列（不一定单调）中找到第一个和第二个大于k的数？

如果我们还是如法炮制，直接维护一个单调栈。
恭喜你，算法假了！
还是这个序列。
1 3 2 6 3 5 7
维护单调栈：
1 3 6 7
如果我们要找到比 4 大的第一个和第二个数，在单调栈里是 6 和 7。
可是正确的应该是 6 和 5 欸。
why？
因为单调栈只能保证最优解不会被剔除，但是次优解可能在最优解后面还比它小，但它仍然可能大于 k。

这时就需要隆重请出全新的神（唐）秘（氏）算法：

二维单调栈

首先我们发现次优解肯定在最优解和原始单调栈中最优解后面的那个数之间（当然也有可能就是后面的那个数）。
而最优解和它后面一个数在原始序列中之间的数又形成了一个新的序列，一个包含次优解的序列 那么对于这个序列我们还可以再维护一个单调栈，用来存储可能的次优解。
也就是说对于在原始单调栈中的每个元素，我们都维护一个单调栈来存储被这个元素 pop 掉的元素

具体实现： 每次放入元素前先将单调栈里比它小的数放进这个元素的单调栈（放进这个元素的单调栈时也要遵守单调栈的规则，也就是要 pop 掉比它小的元素），然后 pop 掉。
需要注意的是，在将比他小的数放入自己单调栈的过程中，我们不需要关心这个元素的单调栈，只要将它本身放入，把它的单调栈全删了，因为这些元素连次优解都不可能是了（毕竟他自己都只可能是次优解了，它栈里的元素只能比它更劣，次优解都不是）。
代码：

vector<pair<node ,vector<node> > > q;//这是我们维护的二维单调栈
vector<node> q1; //这是缓存
for (int i = n; i >= 1; i--)//从后往前放入单调栈
{
  q1.clear();//清空缓存
  while (!q.empty() && q.back().first.val <= a[i])//放入第一维单调栈
  {
    while (!q1.empty() && q1.back().val <= q.back().first.val)//放入第二维单调栈
    {
      q1.pop_back();
    }
    q1.push_back(q.back().first);
    q.pop_back();//将这个元素从第一维单调栈中取出并放入第二维单调栈
  }
  q.push_back(make_pair((node) {a[i], i}, q1));
}
//（关于查询就是两个二分，就不放了doge）

预处理 O(N)，查询虽然是两个二分但是并列的，还是 O(logN) 的，事实上常数应该非常小（毕竟两数直接不会有多少数），应该跑得飞快。

大log当小log，小log当没log
——KevinLikesCoding大神

所以它复杂度应该是常数。

结语

声明：这本来就是一个整活算法，可能没什么应用场景，喜欢用可以用，觉得鸡肋勿喷

我永远喜欢珂朵莉！