单调栈.md

单调栈

模板

func xxx(nums []int) []int {
    stack := make([]int, 0)
    m := len(nums)
    result := make([]int, m)
    
    // 遍历数组
    for i, num := range nums {
        // 栈不为空，且栈顶元素小于当前元素
        for len(stack) > 0 && num > nums[stack[len(stack)-1]] {
            // 栈顶元素出栈
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            
            // 更新结果
            result[top] = process(i) 
        }
        // 栈空或者栈顶元素大于等于当前比较的元素
        // 入栈
        stack = append(stack, i)
    }
    return result
} 

例题

739. 每日温度

739. 每日温度

func dailyTemperatures(temperatures []int) []int {
    stack := make([]int, 0)
    m := len(temperatures)
    result := make([]int, m)

    for i, temperature := range temperatures {
        for len(stack) > 0 && temperature > temperatures[stack[len(stack)-1]] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            result[top] = i - top
        }
        stack = append(stack, i)

    }

    return result
}