Category: Monotonic Queue

	Trick	Difficulty
Sword to Offers Problem 59 Max Queue	Sliding Window Maximum	5 points
LC 456. 132 Pattern	One side monotonic + Greedy	6-7 points
LC 1130 Minimum Cost Tree From Leaf Values	Next Greater + Greedy or DP	6-7 points
LC 1425. Constrained Subset Sum	DP in Linear Structures + Nearest Higher	6 points
LC 1340. Jump Game V	DP in Linear Structures + Nearest Higher	6 points
LC 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit	Sliding Window + Sliding Window Max/Min	6 points
LC 53. Maximum Subarray	Prefix Sum + Greedy	5 points
LC 918. Maximum Sum Circular Subarray	Prefix Sum + Greedy + Circular Structures	5-6 points
LC 901. Online Stock Span	Next Greater (or Longest Interval s.t. Maximum)	5-6 points
LC 1008. Construct Binary Search Tree from Preorder Traversal	Next Greater + Divide & Conquer	5-6 points
LC 42. Trapping Rain Water	Next Greatest + Tricky	6 points
LC 84. Largest Rectangle in Histogram	Next Smaller + Tricky	6 points
LC 496. Next Greater Element I	Next Greater	4 points
LC 503. Next Greater Element II	Next Greater + Circular Array	5 points
LC 739. Daily Temperatures	Next Greater (Longest Qualified Maximum)	5 points

Monotonic Queue Concepts

Posted on May 6, 2020May 25, 2020 by fighternan

Summary Usually, the monotonic queue can be used in the following situations. Next Greater/Greatest: find the first larger or smaller element (or the largest or smallest element) from the current index to the very right index; Sliding Window Max: find the smallest or largest value in a sliding window Length s.t. Max: find the longest…

Sliding Window & Monotonic Queue

Posted on May 3, 2020May 6, 2020 by fighternan

Summary A typical sliding window problem requires the longest or shortest subarray which satisfies certain constraints. The constraint must satisfy a monotonic property: as the right end of the window increases, the left end won’t decrease. If the constrain is related to maximum or minimum, we could use Monotonic Queues, which are perfect data structures…

Monotonic Queue in DP

Posted on April 26, 2020May 6, 2020 by fighternan

Summary In this post, I will introduce some DP problems involving the Monotonic Queue. Details LC 1425. Constrained Subset Sum It is not difficult to get the following O(n^2) solution. However, the complexity is not good. What we need for {alg[i+j] for j=[1, k]} is only the maximum. So we need to keep tracking the…

Monotonic Queue (Pure)

Posted on March 15, 2020June 4, 2020 by fighternan

Summary I will introduce some pure Monotonic Queue problems in this post. Details Sword to Offers Problem 59 Max Queue Mantain a special queue so that you can do max_value, push_back, and pop_front in amortized O(1) time. LC 456. 132 Pattern It is not difficult to get an O(n^2) or even an O(nlogn) solution: we…