单调栈
P5788 【模板】单调栈 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)题目大意:统计每个数后第一个大于该数的数字的位置。
思路: 将数看成是人的身高,每个人向后看都只能看到第一个比自己高的人,矮的看不见,后边更高的也看不见(因为视线被挡住了)。
所以从左向右遍历,当遇到第一个人,当他比他前一位的人高时,那么这个矮人的结果就出来了,让他离开,然后这位高人继续向前比较,直到遇到不比他矮的人,立正等待比他高的出现,他就可以离开了。
显然可以用栈实现
例题二#
1.最大区间 - 蓝桥云课 (lanqiao.cn)
例题三、#
P 6198 [EER 1] 单调栈 - 洛谷 | 计算机科学教育新生态 (luogu. Com. Cn)