Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

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

linkedin
github
slack

Post Views: 16
Posted in ReviewTagged monotone, review

Post navigation

Review: Object-Oriented Design Problems
Series: Palindrome Problems & Follow-Up

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.