CodeBook
  • Introduction
  • Array
    • Maximum Product of Three Numbers
    • Set Mismatch
    • Find the Duplicate Number
    • Find All Duplicates in an Array
    • Find All Numbers Disappeared in an Array
    • Missing Number
    • Single Number
    • Find Difference
    • Find the Celebrity
    • Word Distance
    • Product of Array Except Self
  • Binary Search
    • First Bad Version
    • Search in a Big Sorted Array
    • Search Range
    • Find the Peak
    • Maximum Number in Mountain Sequence
    • Search in Rotated Sorted Array
    • Find Minimum in Rotated Sorted Array
    • Search a 2D Matrix
    • Search a 2D Matrix II
    • Smallest Rectangle Enclosing Black Pixels
    • [Binary Search] Merge Two Sorted Array
    • Single Element in a Sorted Array
  • Two Pointers
    • 1 Forward
      • Moving Zeros
      • Remove Elements
      • Remove Duplicated
      • Longest Continuous Increasing Subsequence
      • Replace all Occurrences of String AB with C
    • 2 Oppsite
      • Rotate Array
      • Container With Most Water
      • Trapping Rain Water
      • Triangle Count
    • 3 Sliding Windows
      • Permutation in String
      • Find All Anagrams in a String
      • Longest Substring with At Most K Distinct Characters
      • Max Consecutive Ones II
      • Minimum Size Subarray Sum
      • Longest Substring Without Repeating Characters
      • Minimum Window Substring
      • Subarrays with K Different Integers
    • 4 Partition
      • Color Sort
      • Color Sort II
      • Partition Array
    • # Sum
      • Two Sum
      • Two Sum - Unique Pairs
      • Two Sum - Less Or Equal
      • Two Sum - Greater Than Target
      • Two Sum - Closest
      • Two Sum - Difference
      • Two Sum - Data Structure Design
      • Three Sum
      • Three Sum With Multiplicity
      • Three Sum Smaller
      • Three Sum - Triangle Count
      • Four Sum
  • BFS
    • 1 Traverse
      • Number of Islands
      • Clone Gragh
      • Number of Distinct Islands
      • Pacific Atlantic Water Flow
      • Surrounded Regions
      • Walls and Gates
      • Max Area of Island
    • 2 Shortest
      • 01 Matrix
      • Knight Shortest Path
      • Shortest Distance from All Buildings
      • Best Meet Point
      • Shortest Bridge
      • Snakes and Ladders
      • Bus Route
  • DFS
    • 0 Basic
      • Subsets
      • Subsets II
      • Permutations
      • Permutations II
      • Prev/Next Permutation
      • Kth Permutation
      • Permutation Index
      • Combination Sum
      • Combination Sum II
      • Combination Sum III
      • Combination
      • Path Sum
    • 1 Enumeration
      • Cartesian Product
      • Letter Combinations of a Phone Number
      • Split String
      • Palindrome Partitioning
      • Expression Add Operators
      • Target Sum
      • Restore IP Addresses
      • Generate Parentheses
      • Generalized Abbreviation
      • Remove Invalid Parentheses
      • Letter Case Permutation
      • Factor Combinations
      • Find the Missing Number II
    • 2 Search
      • N-Queens
      • Sudoku
      • Employee Importance
      • Increasing Subsequences
      • Nested List Weight Sum
    • 3 Flood Fill
      • Flood Fill
      • Number of Enclaves
    • 4 Path
      • Longest Increasing Path in a Matrix
      • Unique Paths III
    • 5 Memo
      • Knight Dialer
      • Regular Expression Matching
      • Wildcard Matching
    • # Word Big Four
      • Word Break
      • Word Break II
      • Word Pattern
      • Word Pattern II
      • Word Search
      • Word Search II
      • Word Ladder
      • Word Ladder II
  • Tree
    • 0 Binary Search Tree
      • Validate Binary Search Tree
      • Recover Binary Search Tree
      • Minimum Absolute Difference in BST
      • Find Mode in Binary Search Tree
      • Verify Preorder Sequence in Binary Search Tree
      • Unique Binary Search Trees
      • Count of Smaller Numbers After Self
      • Trim a Binary Search Tree
      • Closest Binary Search Tree Value
      • Closest Binary Search Tree Value II
    • 1 Traversal
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
    • 2 Divide and Conquer
      • Balanced Binary Tree
      • Max/Min Depth of Binary Tree
      • Diameter of Tree
      • DiffSum
      • Find Leaves of Binary Tree
    • 3 SubTree
      • Same/Symmetric Tree
      • TreeIsomorphism
      • Subtree of Another Tree
      • Find Duplicate Subtrees
      • Most Frequent Subtree Sum
      • Minimum Subtree
      • Subtree with Maximum Average
      • Equal Tree Partition
      • Flip Binary Tree To Match Preorder Traversal
    • 4 Path
      • Path Sum
      • Path Sum II
      • Path Sum III
      • Path Sum IV
      • Path Sum with Digits Representation
      • Binary Tree Paths
      • Binary Tree Longest Consecutive Sequence
      • Binary Tree Longest Consecutive Sequence II
      • Binary Tree Maximum Path Sum
      • Sum Root to Leaf Numbers
      • Boundary of Binary Tree
      • Smallest String Starting From Leaf
    • 5 Level Order
      • Level Order Traversal
      • Maximum Width of Binary Tree
      • Binary Tree Right Side View
      • Binary Tree Vertical Order Traversal
    • 6 LCA
      • LCA
      • LCA II
      • LCA III
      • LCA IV
      • Smallest Deepest Subtree
      • LCA of a BST
      • Cousins in Binary Tree
    • 7 Build Tree
      • Build Maximum Binary Tree
      • Convert Sorted List to Binary Search Tree
      • Serialize Deserialize
      • Verify Preorder Serialization of a Binary Tree
      • Construct Binary Tree from Traversals
    • 8 Distance
      • Closest Leaf in a Binary Tree
      • All Nodes Distance K in Binary Tree
    • 9 Structure
      • Flatten Binary Tree to Linked List
      • Binary Tree Upside Down
      • BST to Doubly LinkedList
      • Populating Next Right Pointers in Each Node
      • Populating Next Right Pointers in Each Node II
      • Invert Binary Tree
    • # N-ary Tree
  • String
    • 1 Pattern
      • Is Subsequence
      • One Edit Distance
      • Backspace String Compare
    • 2 Implementation
      • Reverse
      • Find the Closest Palindrome
      • Reverse Words in a String
      • Text Justification
    • 3 Substring
      • Implement Str
      • Longest Substring with At Least K Repeating Characters
      • Longest Common Prefix
    • 4 Number
      • Maximum Swap
      • Add Strings
      • Nth Digit
      • Compare Version Numbers
      • String to Integer (atoi)
      • Integer to English Words
      • Integer to Roman
      • Roman to Integer
      • Multiply Strings
      • Reverse Integer
    • 5 Decode
      • Decode String
      • Encode and Decode Strings
    • 6 Palindrome
      • Valid Palindrome
      • Valid Palindrome II
      • Palindrome Number
      • Palindrome Linked List
      • Palindromic Substrings
      • Palindrome Permutation
      • Palindrome Partitioning
      • Find Longest Palindromic Substring
      • Longest Palindromic Subsequence
      • Longest Palindromic Substrings
    • 7 Evaluation
      • Solve the Equation
      • Simplify Path
      • Valid Number
    • 8 Binary String
      • Count Binary Substrings
    • 9 Parenthesis
      • Valid Parenthesis String
      • Valid Parentheses
  • Data Structures
    • 0 Design
      • LRU
      • LFU
    • 1 LinkedList
      • Merge Sort
      • Find Cycle
      • Palindrome Linked List
      • Remove Duplicates
      • Flatten a Multilevel Doubly Linked List
      • Copy List with Random Pointer
    • 2 Stack
      • Min Stack
      • Max Stack
      • Implement Queue by Stacks
      • Implement Stack by Queues
    • 3 Queue/Deque
      • Moving Average
      • Design Circular Queue
      • Design Circular Deque
    • 4 Heap
      • Median for Data Stram
      • Kth Largest Data Stream
      • Top K Words
      • Top K Elements
      • Kth Smallest Number in Sorted Matrix
    • 5 Interval
      • Merge Intervals
      • Insert Interval
      • Non-overlapping Intervals
      • Maximum Length of Pair Chain
      • Meeting Room
      • Merge Two Sorted Interval List
      • Merge K Sorted Interval List
      • Intersection of Two Sorted Intervals
      • Meeting Room II
    • 6 Matrix
      • Multiply Sparse Matrix
      • Matrix Diagonal Traverse
      • Valid Sudoku
      • Spiral Matrix
    • 7 Iterator
      • Flatten 2D Vector
      • Pair Iterator
      • Peeking Iterator
      • Zigzag Iterator
    • 8 Hash
      • Design HashSet
      • Design HashMap
      • Hash Function
      • ReHash
      • Consistent Hash
      • Bloom Filter
      • Robin-Karp Algorithm
  • Advanced Data Structures
    • 1 Trie
      • Implement Trie
      • Stream of Characters
    • 2 Union Find
      • Number of Islands II
      • [Union Find]Graph Connect Tree
      • Minimum Spanning Tree
      • Bricks Falling When Hit
      • Most Stones Removed with Same Row or Column
      • Satisfiability of Equality Equations
    • 3 Monotonous Stack
      • Increasing Triplet Subsequence
      • Largest Rectangle in Histogram
      • Maximal Rectangle
      • Remove K Digits
      • Remove Duplicate Letters
      • Next Greater Element I
      • Next Greater Element II
    • 4 TreeSet/TreeMap
      • My Calendar I
      • My Calendar II
    • 5 Random
      • Shuffle an Array
      • Random Pick with Weight
      • Random Pick Index
    • 6 Binary Index Tree
    • 7 Segment Tree
      • Range Sum Query - Mutable
  • Graph
    • 1 General
      • Graph Deep Copy
    • 2 Topological Sorting
      • Course Schedule
      • Sequence Reconstruction
      • Alien Dictionary
    • 3 Bipartition
      • Is Graph Bipartition
      • Possible Bipartition
    • Detect Cycle in an Undirected Graph
    • Shortest Path in Undirected Graph
    • All Paths From Source to Target
    • Graph Valid Tree
    • Number of Connected Components in an Undirected Graph
    • Minimum Height Trees
  • Dynamic Programming
    • 0 Basic DP
      • Triangle
      • House Robber
      • House Robber II
      • Paint Fence
      • Paint House
    • 1 Sequence DP
      • Decode Ways
    • 2 Match Sequence DP
      • Edit Distance
      • K Edit Distance
      • Longest Common Subsequence
      • Minimum Swaps To Make Sequences Increasing
      • Scramble String
    • 3 Interval DP
      • Burst Ballons
      • Stone Game
    • 4 Matrix DP
      • Number Of Corner Rectangles
      • Max Square
      • Longest Increasing Path in a Matrix
    • 5 Backpack
      • K-Sum
      • Backpack1-01
      • Backpack2-01
      • Backpack4-Complete
      • Backpack3-Complete
      • Backpack7-Multiply
    • 6 Game DP
      • Predict the Winner
      • Can I Win
      • Coins In Line I
      • Coins In Line II
      • Coins In Line III
  • Common Methods
    • 1 Presum
      • Subarray Sum Equals K
      • Continuous Subarray Sum
      • Path Sum II
      • Min/Max Subarry
      • Contiguous 01-Array
      • Flip 01String to Monotone Increasing
      • Maximum Sum of Two Non-Overlapping Subarrays
    • 2 Bucket
      • Maximum Gap
    • 3 Simulation
      • Pour Water
    • 4 Buffer
      • Read N Characters Given Read4 II - Call multiple times
      • Read N Characters Given Read4
      • Third Maximum Number
    • 5 Merge/Union
      • Merge k Sorted Lists
      • Merge k Sorted Arrays
      • Merge k Sorted Intervals
      • Intersection of Three Sorted Array
      • Intersection of Two Arrays
      • Intersection of Two Arrays II
    • 6 Geometry
      • Max Points on a Line
    • 7 Math
      • GCD
      • Matrix Coordinate
      • Sqrt(x)
      • Divide Two Integers
      • pow(x, n)
    • 8 Sorting
      • Merge Sort
      • Quick Sort
      • Quick Select
  • Design/OOD
    • Design Rate Limiter
    • Design Hit Counter
    • Design Twitter
    • Design MapWithExpiration
    • Design Tiny URL
  • Appendix
    • Java Built-in
      • Comparator
      • Stream
      • String Pool
    • Multithreading
      • Synchronized
      • Producer-Consumer
      • CountDownLatch
      • Semaphore
      • Thread Pool
      • DeadLock
      • Inter-thread Communication
Powered by GitBook
On this page
  1. Advanced Data Structures

3 Monotonous Stack

单调栈分的细有四种（递增或者递减），主要在于是不是严格单调，看情况和使用场景选用，比如栈里是否存在相等的元素

栈里通常存放下标或者元素，可以正向遍历或者反向遍历

想找 "从当前元素向某一方向的第一个 (大于 / 小于) 自己的元素"，就要靠单调栈来维护单调性，对应的是 (递减 / 递增)。

不用刻意去记（peek大就是递增，小就是递减，有等于时是严格单调），主要想一下什么大小关系会导致栈进行pop，比如

  • What? 栈中只保存升序序列

  • How? 新元素插入前 pop 掉所有比它大的

  • stack([1,2,8,10]).push(5) => stack([1,2,5])

顺便提一下Longest Increasing Subsequence (LIS) 问题，其实和但单调栈思路类似

PreviousSatisfiability of Equality EquationsNextIncreasing Triplet Subsequence

Last updated 6 years ago