单调栈候选淘汰：数据结构与算法实验

互动实验 1 / 5

第一个数 2 右侧下一个更大值是多少？

请根据示例独立推演，再提交验证。

C++ 示例 · 按执行顺序推演

#include <bits/stdc++.h>
using namespace std;

int main() {
vector<int>a{2,1,3},answer(3,-1);stack<int>s;
for(int i=0;i<3;++i){while(!s.empty()&&a[s.top()]<a[i]){answer[s.top()]=a[i];s.pop();}s.push(i);}
cout<<answer[0]<<" "<<answer[2];
}

第一个数 2 右侧下一个更大值是多少？

思路提示

右侧先遇到 1，再遇到更大的 3。

可以回到前一步复查示例，理解后再独立验证。

互动实验 2 / 5

最后一个数右侧没有更大值，本例返回什么？

请根据示例独立推演，再提交验证。

C++ 示例 · 按执行顺序推演

#include <bits/stdc++.h>
using namespace std;

int main() {
vector<int>a{2,1,3},answer(3,-1);stack<int>s;
for(int i=0;i<3;++i){while(!s.empty()&&a[s.top()]<a[i]){answer[s.top()]=a[i];s.pop();}s.push(i);}
cout<<answer[0]<<" "<<answer[2];
}

最后一个数右侧没有更大值，本例返回什么？

思路提示

用 -1 表示不存在。

可以回到前一步复查示例，理解后再独立验证。

互动实验 3 / 5

栈中保存下标而不只是值，有什么作用？

选择符合算法原理和适用条件的一项。

互动实验 4 / 5

题目要求严格更大时，相等值能充当答案吗？

选择符合算法原理和适用条件的一项。

互动实验 5 / 5

单调栈总操作量为什么通常是线性的？

选择符合算法原理和适用条件的一项。

单调栈候选淘汰

准备探索单调栈候选淘汰

第一个数 2 右侧下一个更大值是多少？

最后一个数右侧没有更大值，本例返回什么？

栈中保存下标而不只是值，有什么作用？

题目要求严格更大时，相等值能充当答案吗？

单调栈总操作量为什么通常是线性的？

引导实验已完成。

把发现，变成独立解决问题的能力。