您的位置: 首页 > IT文章 > 单调栈 单调栈 单调栈 单调栈 分类: IT文章 • 2023-03-12 00:10:23 一种重要的数据结构。 栈内维护信息的单调性，递增或递减。 对于插入一个数，如果不满足单调性，则弹出栈顶元素，一直到满足单调性或者栈为空。 应用：对于一个确定高度的矩形，可以确定它的左右边界，即向左找一个第一个比它小的位置，右边也是。 对于一个序列，寻找子序列，使得子序列中的最小值（或其他）乘它的长度（或其他）的值最大。一类的问题，都可以 O(n) 解决。
