Review: Monotone Stack Or Monotone Queue Problems

Posted on January 23, 2018July 26, 2020 by braindenny

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)

Top Questions

Num	Problem	Summary
1	Use monotone stack to find next bigger value	LeetCode: Next Greater Element I
2	Monotone stack for consecutive subarrays	LeetCode: Online Stock Span, LeetCode: Sum of Subarray Minimums
3	Shortest Subarray with Sum at Least K	LeetCode: Shortest Subarray with Sum at Least K
4	Monotone queue	LeetCode: Constrained Subset Sum, LeetCode: Sliding Window Maximum

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
}

See all monotone problems: #monotone

See more blog posts.

Post Views: 16