考虑一个问题：对于一个没有重复数字的序列，求出每个数字右侧第一个比它小的数的下标。很容易可以想到每个数字不断向右遍历，但是复杂度为 $O(n^2)$，有没有更好的办法？
使用栈来维护（下文下标从 $1$ 开始，且栈中的都是下标），不妨考虑序列 $[2,5,6,7,3,4,1,8]$。首先栈为空，压入下标 $1$，然后发现值 $5,6,7$ 都比 $2$ 大且递增，压入下标，此时栈的状况为 $(1,2,3,4$。
再来到下标 $5$，值为 $3$，比栈顶下标 $4$ 代表的值 $7$ 小，此时直接结算 $a[4]$ 的第一个比它小的数就是 $a[5]=3$，弹出 $4$，此时栈为 $(1,2,3$。不难发现，$a[3]$ 仍大于 $a[5]$，继续记录答案，然后弹出，最后发现 $a[1]<a[5]$，不弹出了，将 $5$ 压入栈，得到 $(1,5$。
来到下标 $6$，$a[6]>a[5]$，直接压入，得到 $(1,5,6$。来到下标 $7$，$a[7]$ 比 $a[1],a[5],a[6]$ 都小，那么全部记录答案，压入 $7$，得到 $(7$。来到下标 $8$，$a[8]>a[7]$，压入得到 $(7,8$，此时已经没有后续的数。
最后，弹出 $8,7$，因为没有数”主动“将它们弹出，所以右侧没有比它们小的数。最后，得到右侧第一个比序列中数小的下标为：$[7,5,5,5,7,7,0,0]$（$0$ 表示不存在）
实际上，我们还可以找到对于每个数，左侧第一个比它小的数。在某个数出栈时，这个数下面的数就是左侧第一个比它小的数。比如，上述 $4$ 出栈时，下面是 $3$，故第一个比他小的数就是 $a[3]=6$，也可以得到下面的下标序列：$[0,1,2,3,1,5,0,7]$。
总而言之，对于一个数，谁让它出栈，谁就是右边第一个比它小的数（最后主动出栈意味着不存在）；谁压在它下面，谁就是左边第一个比它小的数（若其在栈底意味着不存在）。
对于含有重复数字的序列，则需要特殊方法处理。
// 这里使用了 1 开始的下标
stack<int> stk;
int a[N], ans[N][2]; // 第二维为 0，是左侧；第二维为 1，是右侧
void compute() {
int idx; // 用于记录弹出的下标
for (int i = 1; i <= n; i++) {
while (stk.size() && a[stk.top()] >= a[i]) {
// 等于栈顶也要弹出，为了保持该单调栈严格大压小的性质
idx = stk.top();
stk.pop();
ans[idx][0] = stk.size() ? stk.top() : 0; // 底下的就是左边第一个比它小的
ans[idx][1] = i; // 现在将它弹出的就是右边第一个比它小的
}
stk.push(i);
}
while (stk.size()) {
idx = stk.top();
stk.pop();
ans[idx][0] = stk.size() ? stk.top() : 0; // 底下的就是左边第一个比它小的
ans[idx][1] = 0; // 自行弹出，说明右边没有比它小的
}
// 由于单调栈内严格遵守大压小的性质，故 ans[i][0] 的答案都是正确的，
// 至于 ans[i][1] 的答案，需要修正右边第一个比它小的数仍为它本身的情况
for (int i = n - 1; i >= 1; i--) { // 第 n 个必定为 -1，不必修正
if (ans[i][1] != 0 && a[ans[i][1]] == a[i]) { // 检查是否仍为它本身
ans[i][1] = ans[ans[i][1]][1];
// 例如 a[9]=3，单调栈运行过程中为了保证严格大压小，相等也要弹出，
// 不妨设 a[11]=3 弹出了 9，那么 ans[9][1]=11，
// 实际上是不对的。但是，ans[11][1] = 1 是正确的，那就把 11 的答案传递给 9，
// 这样就正确了。并且，从右向左修正也保证了正确性。
// 注：如果不进行修正，则某个数会向左找到第一个严格小的数，向右找到第一个
// 小于或等于的数，在一些单调栈有关的题目具有优势
}
}
}
把 ≥ 改为 ≤ 就可以寻找第一个大于的数。
需要注意的是，如果不在意左边，而只在意右边第一个，则相等就不用弹出。
柱状图中最大矩形