esc to dismiss

单调栈

单调栈就是满足单调性的栈结构,所谓单调性就是说栈内的元素满足简单的规则:比如升序或降序排列。

典型的单调栈题目做题模式比较明显,即:

for i, v := range T {
    // 判断条件,将栈顶元素与将入栈元素比较,如果不满足单调性,则出栈,一直到符合单调性的元素为止
    for len(mono) > 0 && T[mono[len(mono)-1]] < v {
        mono = mono[:len(mono)-1]
    }
    // 元素入栈
    mono = append(mono, i)
}

典型的题目如 739. 每日温度

需要触类旁通的如 962. 最大宽度坡 ,这里的单调栈的属性是确定的,只是在入栈和出栈的判断不是同一个条件。

x