Review: Monotone Stack Or Monotone Queue Problems

Posted on January 23, 2018October 8, 2019 by braindenny

Scenarios

Name	Summary
Use monotone stack to find next bigger value	Leetcode: Next Greater Element I
Use monotone stack for consecutive subarrays	Leetcode: Online Stock Span, Leetcode: Sum of Subarray Minimums
Monotone queue, instead of monotone stack	Leetcode: Shortest Subarray with Sum at Least K

Basic Abstractions

Name	Summary
Order of elements in stack	It would be monotone
Elements remained monotone in stack	They indicates undecided elements
Elements in stack is usually index, instead of objects
May not need to store the array of indices	Leetcode: Next Greater Element I
Mistake: when pop stack, don’t compare value with index	for len(stack)>0 && nums[stack[len(stack)-1]]>v VS for len(stack)>0 && stack[len(stack)-1]>v
Initial value of the indices array	-1 VS len(array)

Scenarios

Find next bigger value or smaller value for each elements of an array

Code Skeleton

// Blog link: https://code.dennyzhang.com/number-of-valid-subarrays
// Basic Ideas: Monotone stack
//    Find the next bigger value for a given element
// Complexity: Time O(n), Space O(n)
func validSubarrays(nums []int) int {
    l := make([]int, len(nums))
    for i, _ := range l {
        l[i] = len(nums)
    }
    stack := []int{}
    for i, v := range nums {
        for len(stack) > 0 && nums[stack[len(stack)-1]] > v {
            l[stack[len(stack)-1]] = i
            stack = stack[0:len(stack)-1]
        }
        stack = append(stack, i)
    }

    res := 0
    for i, _ := range nums {
        res += l[i]-i
    }
    return res
}

CheatSheet: Leetcode For Code Interview

See all monotone problems: #monotone

See more blog_posts.

Post Views: 16