栈有着广泛的应用,比如逆波兰表达式,表达式求值,迷宫问题求解,程序调用等,不过这些问题今天都不涉及哈哈哈哈。关于程序执行期间,各个函数的相互调用使用的调用栈,可以参考这里。
单调栈属于栈的具体应用,而非栈这种数据结构的简单使用。此类问题一般用于求解以下场景:序列中某个元素的下一个最大元素,元素间的最大跨度,维持某一状态持续的最长时间等。以序列 [2,1,3,4]
为例,1 的下一个最大元素就是 3,而不是 4;最大上升的跨度为从 2 到 4,跨越了 2 个数。对于这种问题都可以用单调栈求解。