Review: Monotone Stack Or Monotone Queue Problems

**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

- Review: Monotone Stack Or Monotone Queue Problems
- LeetCode: Verify Preorder Sequence in Binary Search Tree
- LeetCode: Sliding Window Maximum
- LeetCode: Shortest Subarray with Sum at Least K
- LeetCode: Online Stock Span
- LeetCode: Number of Valid Subarrays
- LeetCode: Next Greater Node In Linked List
- LeetCode: Next Greater Element II
- LeetCode: Next Greater Element I
- LeetCode: Maximum Width Ramp
- LeetCode: Maximum Binary Tree
- LeetCode: Maximal Rectangle
- LeetCode: Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
- LeetCode: Largest Rectangle in Histogram
- LeetCode: Daily Temperatures
- LeetCode: Constrained Subset Sum
- LeetCode: Constrained Subsequence Sum

See more blog posts.