Review: Monotone Stack Or Monotone Queue Problems Posted on January 23, 2018July 26, 2020 by braindenny 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 } CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups See all monotone problems: #monotone Review: Monotone Stack Or Monotone Queue ProblemsLeetCode: Verify Preorder Sequence in Binary Search TreeLeetCode: Sliding Window MaximumLeetCode: Shortest Subarray with Sum at Least KLeetCode: Online Stock SpanLeetCode: Number of Valid SubarraysLeetCode: Next Greater Node In Linked ListLeetCode: Next Greater Element IILeetCode: Next Greater Element ILeetCode: Maximum Width RampLeetCode: Maximum Binary TreeLeetCode: Maximal RectangleLeetCode: Longest Continuous Subarray With Absolute Diff Less Than or Equal to LimitLeetCode: Largest Rectangle in HistogramLeetCode: Daily TemperaturesLeetCode: Constrained Subset SumLeetCode: Constrained Subsequence Sum See more blog posts. Post Views: 16 Post navigation Review: Object-Oriented Design ProblemsSeries: Palindrome Problems & Follow-Up Leave a Reply Cancel replyYour email address will not be published.Comment Name Email Website