| 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 |
Category: Monotonic Queue
Monotonic Queue Concepts
Posted on
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
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
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
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…