单调栈
找到每个数左边离他最近且比他小的数。
3 4 2 7 5
-1 3 -1 2 2
考虑方式和双指针类似。
先考虑 找到每个数左边离他最近且比他小的数 这个问题的暴力做法:二重循环
for (int i = 0, j; i < n; i ++) {
for (j = i - 1; j >= 0; j --) {
if (a[j] < a[i]) {
cout << a[j] << ' ';
break;
}
}
if (j == -1) {
cout << -1 << ' ';
}
}
首先要研究的就是 i, j
的位置关系。比如是否可以让 j
不从 i - 1
开始移动,而是观察当 i
向右移动一位之后,j
对应的移动方式。
注意到:针对 a[i + 1]
和 a[i]
的大小关系可分为两种情况:
,则 a[i + 1]
左边离它最近且比它小的数就是a[i]
,由于 ,那么 j
只能不动或者左移- 也就是说,
j
的取值是呈现 要么跳跃,要么一个一个左移 的情形
cout << -1 << " ";
for (int i = 1, j = 0; i < n; i ++) {
if (a[i] > a[i - 1]) {
j = i - 1;
cout << a[i - 1] << " ";
continue;
}
for (j; j >= 0; j --) {
if (a[j] < a[i]) {
cout << a[j] << " ";
break;
}
}
if (j == -1) {
cout << -1 << ' ';
}
}
上述代码已经可以 AC 了,我们继续思考:j
的跳跃会出现这种情况吗?
如果不会,那么显然由于 i, j
的遍历都是最多遍历每个点一次,那么时间复杂度最多是
于是我们继续思考当
:这说明 j
保持不变即可:这是最不愿意发生的事,说明 j
要左移了- 由于
是最靠近 且比它小的数,因此在 的左边可能会有比它更小的数 1 3 4 5 2
就是例子,当j
跳跃到a[2] = 4
时,下一步要回退两格到1
- 由于
这么说,时间复杂度没法下降了?幸运的是,我们还是有点发现的:那就是我们寻找的是
欸?这个问题为什么这么似曾相识?我们变换一下说法:当
因此可以考虑用 栈 来存储这样的数据。
- 对于任意数据
,此时栈顶存放它左边且最靠近 且比它小的数 - 首先将
入栈 - 栈内满足:每次弹出元素
的左边且最靠近且比它小的元素 来到栈顶 - 这是因为压栈的时候就是按照这个方式压入栈的
- 栈内保持单调递减
- 首先将
- 对于下个数据
,维护方法为: - 如果
,说明栈顶 是满足要求的数,无操作 - 如果
,说明栈顶 不满足要求,弹出 - 由于栈的性质,新栈顶
就是刚才最靠近 且比它小的数,与 进行比较 - 重复上述操作,直到找到要求的数 或者 栈空
- 操作完成后,记得要将
入栈
- 如果
每次操作完成后都将当前数入栈这一操作:保证了下次遇到
核心代码:
// ...
for (int i = 0; i < n; i ++) {
int x;
cin >> x;
while (tt && stk[tt] >= x) {
tt --;
}
if (tt) {
cout << stk[tt] << " ";
}
else {
cout << -1 << " ";
}
stk[++ tt] = x;
}
以上这种思考逻辑完全是正向的:
- 首先思考
i, j
之间的关系:j
一定是跳跃 + 左移两种情况的 - 然后发现
j
在左移的过程中,是不需要考虑左边比它大的数的 - 然后发现结构的不变性:找到的是
左边最靠近且比它小的数 ,循环操作 - 最后考虑用栈存储它们:
- 压入栈的方式为:每次保证栈顶都是最靠近
且比他小的数后压入 - 弹出栈的情况为:每次弹出后都保证栈顶是最靠近且比它小的数
- 压入栈的方式为:每次保证栈顶都是最靠近
另一种思考方式
对于序列
- 如果比
大,那么向左搜索到 就停止了,不会取到 - 如果比
小,那么会直接跳过
因此在我们考察
假设我们现在已经有了一个这样的序列,我们来探究如何维护它:
- 序列最右边的元素为
,待考察的元素为 ,我们要找到它对应的答案 - 首先该序列已经去掉了所有永远不会成为答案的数,剩下的数分两种情况讨论:
:无问题,直接将 插入依然是严格单调递增序列,答案是 :此时在备选答案序列中从右往左查询,找到的第一个比 小的数就是最靠近 且比它小的数 了 - 而对于
中的所有数,它们对于 以及后面的数(由于和 构成了逆序对)因此不会成为答案
对于这种只考虑 从右往左 查询(某一个方向)的数据结构,我们可以用栈来存储,也就是从顶往下查询。
- 对于待考察元素
a[i]
- 考虑栈顶元素
stk[tt]
和它的大小关系stk[tt] < a[i]
,则答案为stk[tt]
,直接加入a[i]
,依然是单调栈stk[tt] >= a[i]
,则不断弹出栈顶元素tt --
,直到栈顶元素符合要求- 这一步也就是单调栈维护(清除逆序对)的做法
似乎这种思考方式更清爽简洁(逆序对中较大的数不会成为后面的答案),但是较难想到。
用 STL 的 stack
再写一次: