刷题技巧：单调栈
发布时间
阅读量：
阅读量
#单调栈理论
其定义为何？
从字面意义出发，这种数据结构的特点在于栈内元素始终维持着单调递增或单调递减的状态。当引入新的元素时，若该元素符合当前的单调性要求，则直接将其压入栈中；若不符合，则持续将栈顶元素弹出，直至满足单调条件为止。换句话说，新元素必须被压入栈中，而所有不满足条件的旧元素则会被依次移除。
适用场景为何？
应用场景：当需要高效地确定某一位置左右两侧第一个比它大（或小）的数值所在位置时，可采用单调栈技术，其时间复杂度为O(n)。
#确定当前数值的下一个（更小、更大）数值
#确定当前数值的上一个（更小、更大）数值
实现方式如何？
采用单调递增栈的方式：
#单调递增栈
#找到下一个更小的值
#找到上一个更小的值
def nextGreaterNum(a):
print a
#栈中存的是数字对应下标
stack = []
#若没有下一个比它更大的数字，那么这个位置就是-1
res = [-1 for x in a]
res_1 = [-1 for x in a]
for i in range(len(a)):
print全部评论 (0)
还没有任何评论哟~