OJ
  • Introduction
  • Some Tips
  • strStr and Coding Style
  • Binary Search
    • 1283. Find the Smallest Divisor Given a Threshold
    • 1898. Maximum Number of Removable Characters
    • 162. Find Peak Element
    • 540. Single Element in a Sorted Array
    • First Position of Target
    • 34. Find First and Last Position of Element in Sorted Array
    • Guess Number Higher or Lower
    • First Bad Version
    • Search Insert Position
    • Search in a Big Sorted Array
    • Convert Binary Search Tree to Sorted Doubly Linked List
    • Search a 2D Matrix
    • 981. Time Based Key-Value Store
    • 362. Design Hit Counter
    • 1348. Tweet Counts Per Frequency
    • 153. Find Minimum in Rotated Sorted Array
    • 33. Search in Rotated Sorted Array
    • Search in Rotated Sorted Array II
    • Heaters
    • Find Right Interval
    • 1060. Missing Element in Sorted Array
    • Is Subsequence
    • Search a 2D Matrix II
    • Find K Closest Elements
    • H-Index II
    • Minimum Size Subarray Sum
    • Median of Two Sorted Arrays
    • 302. Smallest Rectangle Enclosing Black Pixels
    • Longest Increasing Subsequence
      • Russian Doll Envelopes
      • 334. Increasing Triplet Subsequence
    • 二分Range
      • Sqrt
      • Wood Cut
      • Kth Smallest Element in a Sorted Matrix
      • 719. Find K-th Smallest Pair Distance
      • Capacity To Ship Packages Within D Days
      • 668. Kth Smallest Number in Multiplication Table
      • 774. Minimize Max Distance to Gas Station
      • 1631. Path With Minimum Effort
      • 1201. Ugly Number III
    • Find the Unique Number
  • Binary Tree & Divide Conquer
    • Binary Search Tree
      • 1008. Construct Binary Search Tree from Preorder Traversal
      • 449. Serialize and Deserialize BST
      • 109. Convert Sorted List to Binary Search Tree
      • Trim a Binary Search Tree
      • Two Sum IV - Input is a BST
      • Convert BST to Greater Tree
      • 270. Closest Binary Search Tree Value
      • Find Mode in Binary Search Tree
      • Kth Smallest Element in a BST
      • Delete Node in a BST
      • 98. Validate Binary Search Tree
      • Unique Binary Search Trees II
      • 285. Inorder Successor in BST
      • Count of Smaller Numbers After Self
      • 99. Recover Binary Search Tree
      • 235. Lowest Common Ancestor of a Binary Search Tree
      • 295. Find Median from Data Stream
      • 938. Range Sum of BST
      • 1146. Snapshot Array
      • 480. Sliding Window Median
    • Divide & Concquer
      • 226. Invert Binary Tree
      • Insufficient Nodes in Root to Leaf Paths
      • Convert Sorted Array to Binary Search Tree
      • Maximum Depth of Binary Tree
      • 1430. Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree
      • Balanced Binary Tree
      • Binary Tree Tilt
      • 617. Merge Two Binary Trees
      • 100. Same Tree
      • 543. Diameter of Binary Tree
        • Largest BST Subtree
        • Longest Univalue Path
        • 549. Binary Tree Longest Consecutive Sequence II
        • 124. Binary Tree Maximum Path Sum
      • 865. Smallest Subtree with all the Deepest Nodes
      • Second Minimum Node In a Binary Tree
      • Path Sum
        • Path Sum IV
        • Sum Root to Leaf Numbers
        • 437. Path Sum III
      • 236. Lowest Common Ancestor of a Binary Tree
      • 111. Minimum Depth of Binary Tree
      • Maximum Binary Tree
      • Most Frequent Subtree Sum
      • 114. Flatten Binary Tree to Linked List
      • 834. Sum of Distances in Tree
      • 1443. Minimum Time to Collect All Apples in a Tree
      • Construct Binary Tree from Preorder and Inorder Traversal
      • Construct Binary Tree from Inorder and Postorder Traversal
      • Count Complete Tree Nodes
      • Populating Next Right Pointers in Each Node
      • Binary Tree Longest Consecutive Sequence
      • Sum of Left Leaves
      • 87. Scramble String
      • LCA of the Deepest Nodes
      • 统计Distance和覆盖
        • Sum of Distances in Tree
    • Path-recorder Depth-first Search
      • Binary Tree Paths
      • 863. All Nodes Distance K in Binary Tree
      • 606. Construct String from Binary Tree
      • 1367. Linked List in Binary Tree
      • 1343. Maximum Product of Splitted Binary Tree
      • 1457. Pseudo-Palindromic Paths in a Binary Tree
    • Order Traversal
      • Serialize and Deserialize Binary Tree
      • 958. Check Completeness of a Binary Tree
      • 742. Closest Leaf in a Binary Tree
      • Find Duplicate Subtrees
    • 919. Complete Binary Tree Inserter
    • 1519. Number of Nodes in the Sub-Tree With the Same Label
    • 307. Range Sum Query - Mutable
    • 428. Serialize and Deserialize N-ary Tree
    • 315. Count of Smaller Numbers After Self
      • 308. Range Sum Query 2D - Mutable
      • 493. Reverse Pairs
  • Dynamic Programming I
    • 走格
      • 119. Pascal's Triangle II
      • Unique Paths
      • Unique Paths II
      • Climbing Stairs
      • 64. Minimum Path Sum
      • 741. Cherry Pickup
      • Knight Probability in Chessboard
      • Triangle
      • 221. Maximal Square
      • Bomb Enemy
      • 935. Knight Dialer
      • 174. Dungeon Game
      • 818. Race Car
      • 329. Longest Increasing Path in a Matrix
      • 403. Frog Jump
      • 568. Maximum Vacation Days
      • 1344. Jump Game V
    • Subsequence
      • Longest Increasing Subsequence
      • 1395. Count Number of Teams
      • 1027. Longest Arithmetic Sequence
      • Number of Longest Increasing Subsequence
      • Wiggle Subsequence
      • Largest Divisible Subset
      • Maximum Length of Pair Chain
      • 940. Distinct Subsequences II
      • 727. Minimum Window Subsequence
      • Burst Balloons
      • 1458. Max Dot Product of Two Subsequences
      • 1696. Jump Game VI
      • 1626. Best Team With No Conflicts
    • Counting Bits
    • 887. Super Egg Drop
    • 674. Longest Continuous Increasing Subsequence
    • Integer Break
    • Catalan Number
      • Unique Binary Search Trees
      • 22. Generate Parentheses
      • All Possible Full Binary Trees
    • Count Numbers with Unique Digits
    • 2 Keys Keyboard
    • 背包问题
      • Partition Equal Subset Sum
      • 494. Target Sum
      • Ones and Zeroes
      • Perfect Squares
      • Coin Change
      • Combination Sum IV
      • pre背包
        • House Robber
        • House Robber II
      • Coin Change 2
      • 630. Course Schedule III
      • 920. Number of Music Playlists
      • 1235. Maximum Profit in Job Scheduling
      • 1262. Greatest Sum Divisible by Three
    • DFS + Memorization
      • 1444. Number of Ways of Cutting a Pizza
    • Palindromic Strings
      • Palindromic Substrings
      • 5. Longest Palindromic Substring
      • Longest Palindromic Subsequence
      • 1312. Minimum Insertion Steps to Make a String Palindrome
      • 1216. Valid Palindrome III
      • Palindrome Partitioning II
    • 多状态DP
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock with Cooldown
      • Maximum Product Subarray
      • Paint Fence
      • Best Time to Buy and Sell Stock with Transaction Fee
      • Best Time to Buy and Sell Stock IV
      • 975. Odd Even Jump
      • 801. Minimum Swaps To Make Sequences Increasing
      • 552. Student Attendance Record II
    • f长度与input array长度无关
      • Unique Substrings in Wraparound String
    • 多指针
      • Ugly Number II
      • Super Ugly Number
    • Partition
      • 410. Split Array Largest Sum
      • 664. Strange Printer
      • 1335. Minimum Difficulty of a Job Schedule
      • 471. Encode String with Shortest Length
      • 1473. Paint House III
    • Subarray Sum
      • 304. Range Sum Query 2D - Immutable
      • Range Sum Query - Immutable
      • 689. Maximum Sum of 3 Non-Overlapping Subarrays
      • 53. Maximum Subarray
      • Bitwise ORs of Subarrays
      • 363. Max Sum of Rectangle No Larger Than K
      • 901. Online Stock Span
        • 907. Sum of Subarray Minimums
        • 2104. Sum of Subarray Ranges
    • String Match
      • Regular Expression Matching
      • 32. Longest Valid Parentheses
      • 161. One Edit Distance
      • Word Break
      • Decode Ways
        • 639. Decode Ways II
      • KMP
        • 214. Shortest Palindrome
      • Wildcard Matching
      • 97. Interleaving String
      • 1392. Longest Happy Prefix
    • Game Theory
      • Flip Game II
      • Predict the Winner
      • 843. Guess the Word
    • Flip String to Monotone Increasing
    • 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance
    • Maximum Rectangle
    • 1513. Number of Substrings With Only 1s
    • 哈密顿图
      • 1349. Maximum Students Taking Exam
      • 943. Find the Shortest Superstring
  • Dynamic Programming II
    • 72. Edit Distance
    • Distinct Subsequences
    • Longest Common Substring
    • Longest Common Subsequence
    • Interleaving String
    • House Robber III
  • Linked List
    • 203. Remove Linked List Elements
    • Delete Node in a Linked List
    • Partition List
    • Copy List with Random Pointer
    • Merge k Sorted Lists
    • 148. Sort List
    • Delete Node in a Linked List
    • Merge Two Sorted Lists
    • Add Two Numbers II
    • Swap Nodes in Pairs
    • 2 Pointers with One First Moved N Steps
      • 160. Intersection of Two Linked Lists
      • Remove Nth Node From End of List
      • Rotate List
    • Selection Sort List
    • Insertion Sort List
    • 708. Insert into a Cyclic Sorted List
    • 430. Flatten a Multilevel Doubly Linked List
    • Reverse List
      • 25. Reverse Nodes in k-Group
      • Reverse Linked List
      • Reverse Linked List II
      • Palindrome Linked List
      • Reorder List
    • Remove Nodes
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Sorted List II
    • 876. Middle of the Linked List
    • Linked List Cycle
    • Split Linked List in Parts
  • Array & Numbers
    • 1472. Design Browser History
    • 1291. Sequential Digits
    • 419. Battleships in a Board
    • 48. Rotate Image
    • Perform String Shifts
    • 41. First Missing Positive
    • 73. Set Matrix Zeroes
    • 88. Merge Sorted Array
    • 1347. Minimum Number of Steps to Make Two Strings Anagram
    • Partition Array
    • Median of two Sorted Arrays
    • Reverse Vowels of a String
    • 825. Friends Of Appropriate Ages
    • K-diff Pairs in an Array
    • Longest Word in Dictionary through Deleting
    • Presum
      • Subarray Sum
      • 1352. Product of the Last K Numbers
      • 238. Product of Array Except Self
      • Maximum Subarray II
      • 523. Continuous Subarray Sum
      • Subarray Sum Closest
      • Find Pivot Index
      • 918. Maximum Sum Circular Subarray
      • 930. Binary Subarrays With Sum
      • 974. Subarray Sums Divisible by K
    • Spiral Matrix
      • Spiral Matrix II
      • Spiral Matrix III
      • 498. Diagonal Traverse
      • 766. Toeplitz Matrix
    • Intervals
      • 56. Merge Intervals
      • 352. Data Stream as Disjoint Intervals
      • Merge Two Interval Lists
      • Insert Interval
      • Meeting Rooms
      • 1094. Car Pooling
      • 986. Interval List Intersections
      • 715. Range Module
    • 状态机
      • Game of Life
    • Find All Numbers Disappeared in an Array
    • 406. Queue Reconstruction by Height
    • Flip String to Monotone Increasing
    • Find the Celebrity
    • 扫描线
      • The Skyline Problem
      • 253. Meeting Rooms II
        • 850. Rectangle Area II
        • 732. My Calendar III
      • 759. Employee Free Time
      • 1674. Minimum Moves to Make Array Complementary
    • 463. Island Perimeter
    • 665. Non-decreasing Array
    • 逆推手牌
    • 1354. Construct Target Array With Multiple Sums
    • 780. Reaching Points
    • Rotate Array
    • 969. Pancake Sorting
    • 151. Reverse Words in a String
    • Partition
      • K Empty Slots
    • Sorting
      • 910. Smallest Range II
      • Two City Scheduling
      • 791. Custom Sort String
      • 164. Maximum Gap
      • 1005. Maximize Sum Of Array After K Negations
    • 1006. Clumsy Factorial
    • 1007. Minimum Domino Rotations For Equal Row
    • 896. Monotonic Array
    • 1333. Filter Restaurants by Vegan-Friendly, Price and Distance
    • 1351. Count Negative Numbers in a Sorted Matrix
      • Leftmost Column with at Least a One
    • 1366. Rank Teams by Votes
    • 1332. Remove Palindromic Subsequences
    • 1375. Bulb Switcher III
    • 1389. Create Target Array in the Given Order
    • 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
    • 448. Find All Numbers Disappeared in an Array
    • 1422. Maximum Score After Splitting a String
    • 280. Wiggle Sort
  • Heap
    • Merge k Sorted Arrays
    • Heapify
    • 1046. Last Stone Weight
    • Merge k Sorted Lists
    • Ugly Number
    • 373. Find K Pairs with Smallest Sums
    • 1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows
    • 857. Minimum Cost to Hire K Workers
    • 选出出现频率最高的K个
      • Top K Frequent Words
      • Sort Characters By Frequency
      • 347. Top K Frequent Elements
    • Design Twitter
    • Median of K Sorted Array
    • 239. Sliding Window Maximum
    • 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
    • 1705. Maximum Number of Eaten Apples
    • 1425. Constrained Subsequence Sum
  • Hash
    • Rehashing
    • Longest Consecutive Sequence
    • Distribute Candies
    • Valid Anagram
    • 统计频率
      • Longest Palindrome
      • Number of Boomerangs
      • Longest Harmonious Subsequence
      • Brick Wall
      • 266. Palindrome Permutation
      • Pairs of Songs With Total Durations Divisible by 60
      • 1394. Find Lucky Integer in an Array
      • 1497. Check If Array Pairs Are Divisible by k
    • Overlapping
      • Minimum Index Sum of Two Lists
      • Keyboard Row
      • Implement Magic Dictionary
      • Valid Sudoku
      • 1452. People Whose List of Favorite Companies Is Not a Subset of Another List
    • 见过
      • Isomorphic Strings
      • 1346. Check If N and Its Double Exist
      • Two Sum
      • 1396. Design Underground System
      • Word Pattern
      • 957. Prison Cells After N Days
      • 939. Minimum Area Rectangle
      • Contains Duplicate II
      • 49. Group Anagrams
      • Counting Elements
      • 249. Group Shifted Strings
      • Bulls and Cows
      • 146. LRU Cache
      • 460. LFU Cache
      • First Unique Number
      • 432. All O`one Data Structure
      • 336. Palindrome Pairs
      • 1282. Group the People Given the Group Size They Belong To
      • 166. Fraction to Recurring Decimal
      • Unique Word Abbreviation
      • Task Schedule with Original Order
      • Word Abbreviation
      • 1487. Making File Names Unique
      • 1365. How Many Numbers Are Smaller Than the Current Number
    • Presum
      • Longest Well-Performing Interval
      • 325. Maximum Size Subarray Sum Equals k
      • 525. Contiguous Array
      • Subarray Sum Equals K
    • Counting Sort
      • H-Index
    • Longest Consecutive Sequence
  • Multiple Pointers
    • 双指针之先后指针
      • 283. Move Zeroes
      • 27. Remove Element
      • 26. Remove Duplicates from Sorted Array
      • 80. Remove Duplicates from Sorted Array II
      • 228. Summary Ranges
      • 369. Plus One Linked List
      • 443. String Compression
      • 925. Long Pressed Name
    • Sliding Window
      • Static Size
        • 567. Permutation in String
        • Find All Anagrams in a String
        • 1297. Maximum Number of Occurrences of a Substring
        • Substring with Concatenation of All Words
        • Contains Duplicate III
        • 1456. Maximum Number of Vowels in a Substring of Given Length
      • Dynamic Window
        • Longest Substring Without Repeating Characters
        • 424. Longest Repeating Character Replacement
        • 1248. Count Number of Nice Subarrays
        • 340. Longest Substring with At Most K Distinct Characters
        • 395. Longest Substring with At Least K Repeating Characters
        • Minimum Window Substring
        • 1004. Max Consecutive Ones III
        • 1658. Minimum Operations to Reduce X to Zero
        • 209. Minimum Size Subarray Sum
    • 75. Sort Colors
    • 125. Valid Palindrome
      • Valid Palindrome II
    • Two Sum
      • 15. 3Sum
      • 1498. Number of Subsequences That Satisfy the Given Sum Condition
      • 16. 3Sum Closest
      • 4Sum
      • Sum of Square Numbers
      • 977. Squares of a Sorted Array
      • Container With Most Water
      • Trapping Rain Water
      • 259. 3Sum Smaller
      • 360. Sort Transformed Array
      • 611. Valid Triangle Number
    • Floyd Cycle
      • 202. Happy Number
      • 142. Linked List Cycle II
      • Linked List Cycle
      • 287. Find the Duplicate Number
    • Permutation
      • 31. Next Permutation
      • Previous Permutation
    • Zigzag Iterator
    • 632. Smallest Range Covering Elements from K Lists
    • Strobogrammatic Number
    • Quick Select
      • Kth Largest Element in an Array
      • K Closest Points
    • 349. Intersection of Two Arrays
      • 350. Intersection of Two Arrays II
  • Stack
    • Implement Queue by Two Stacks
    • 155. Min Stack
    • Implement Stack using Queues
    • 结合前面的输入
      • 20. Valid Parentheses
      • Evaluate Reverse Polish Notation
      • Baseball Game
      • 71. Simplify Path
      • Longest Absolute File Path
    • 维持递增或递减
      • 84. Largest Rectangle in Histogram
        • Maximal Rectangle
        • 1504. Count Submatrices With All Ones
      • Next Greater Element I
        • 503. Next Greater Element II
        • Next Greater Node In Linked List
      • Remove Duplicate Letters
      • 132 Pattern
    • Nested
      • 341. Flatten Nested List Iterator
      • 339. Nested List Weight Sum
      • Basic Calculator
      • Decode String
      • Mini Parser
      • 726. Number of Atoms
      • Exclusive Time of Functions
      • 227. Basic Calculator II
      • 772. Basic Calculator III
      • 1096. Brace Expansion II
    • Tree Traversal
      • Binary Tree Preorder Traversal
      • Path Sum II
      • Subtree of Another Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Search Tree Iterator
      • Reconstruct Itinerary
      • Sum of Left Leaves
  • Breadth-first Search
    • Employee Importance
    • Remove Invalid Parentheses
    • Word Ladder II
    • 773. Sliding Puzzle
    • 407. Trapping Rain Water II
    • Level-order Traversal
      • Matrix Cells in Distance Order
      • Average of Levels in Binary Tree
      • Populating Next Right Pointers in Each Node II
      • Sum of Left Leaves
      • 107. Binary Tree Level Order Traversal II
      • Symmetric Tree
      • Find Bottom Left Tree Value
      • Find Largest Value in Each Tree Row
      • Add One Row to Tree
      • Binary Tree Right Side View
      • Binary Tree Zigzag Level Order Traversal
      • 1376. Time Needed to Inform All Employees
      • 1377. Frog Position After T Seconds
      • Clone Graph
      • index
        • 662. Maximum Width of Binary Tree
        • Binary Tree Vertical Order Traversal
        • 987. Vertical Order Traversal of a Binary Tree
        • Print Binary Tree
      • 267. Serialize and Deserialize Binary Tree
    • Letter Combinations of a Phone Number
    • 1197. Minimum Knight Moves
    • 247. Strobogrammatic Number II
    • 1298. Maximum Candies You Can Get from Boxes
    • 1311. Get Watched Videos by Your Friends
    • 1391. Check if There is a Valid Path in a Grid
    • 815. Bus Routes
    • 扫格
      • Walls and Gates
      • Minesweeper
      • 01 Matrix
      • 1293. Shortest Path with Obstacles Elimination
      • Pacific Atlantic Water Flow
      • The Maze II
      • The Maze
      • The Maze III
      • 1036. Escape a Large Maze
      • 317. Shortest Distance from All Buildings
    • Topological Sort
      • Course Schedule
      • 210. Course Schedule II
      • Build Robot
      • 269. Alien Dictionary
        • 953. Verifying an Alien Dictionary
  • Bit Manipulation
    • XOR
      • Single Number
      • 137. Single Number II
      • 260. Single Number III
      • Set Mismatch
      • Missing Number
      • 1310. XOR Queries of a Subarray
      • 1442. Count Triplets That Can Form Two Arrays of Equal XOR
      • Find the Difference
      • Hamming Distance
      • Maximum XOR of Two Numbers in an Array
    • Hash
      • Repeated DNA Sequences
    • AND
      • Power of Two
      • 201. Bitwise AND of Numbers Range
    • Total Hamming Distance
    • 190. Reverse Bits
  • Math
    • Geometry
      • Largest Triangle Area
      • 593. Valid Square
    • Count Primes
    • 441. Arranging Coins
    • Permutation Sequence
    • Range Addition II
    • 进制转换
      • Excel Sheet Column Title
      • Excel Sheet Column Number
      • 405. Convert a Number to Hexadecimal
      • 660 Remove 9
    • Maximum Product of Three Numbers
    • Power of Three
    • Ugly Number
    • 1344. Angle Between Hands of a Clock
    • 66. Plus One
    • 780. Reaching Points
    • 564. Find the Closest Palindrome
    • Sqrt(x)
      • Valid Perfect Square
      • 1390. Four Divisors
    • Factorial Trailing Zeroes
    • Strobogrammatic Number
    • 296. Best Meeting Point
    • 排列组合
      • 1643. Kth Smallest Instructions
    • Perfect Number
    • 加法
      • 67. Add Binary
      • Add Strings
      • Multiply Strings
    • Nth Digit
    • Roman to Integer
      • Integer to Roman
      • Integer to English Words
    • Pow(x, n)
    • Divide Two Integers
    • GCD
    • Geometry
      • Max Points on a Line
      • Rectangle Area
      • Line Reflection
    • Super Pow
    • 829. Consecutive Numbers Sum
    • 找规律
      • Rotate Function
      • Bulb Switcher
      • Add Digits
      • 1247. Minimum Swaps to Make Strings Equal
      • Bulb Switcher II
      • 1503. Last Moment Before All Ants Fall Out of a Plank
    • Next Closest Time
    • 1362. Closest Divisors
    • Missing Ranges
    • Strobogrammatic Number III
    • 1154. Day of the Year
    • 1360. Number of Days Between Two Dates
    • Majority Element
      • Majority Element II
    • 311. Sparse Matrix Multiplication
    • Maximum Swap
    • Reservoir Sampling
      • Random Pick Index
      • 382. Linked List Random Node
    • Integer Break
    • Largest Perimeter Triangle
    • 1363. Largest Multiple of Three
    • Binary Prefix Divisible By 5
    • 随机数
      • 470. Implement Rand10() Using Rand7()
      • 478. Generate Random Point in a Circle
      • 528. Random Pick with Weight
      • 710. Random Pick with Blacklist
      • 381. Insert/Del GetRandom O(1)-Duplicates allowed
  • Trie
    • Replace Words
    • 208. Implement Trie (Prefix Tree)
    • 211. Add and Search Word - Data structure design
      • Add and Search Word with Regular Expression - Data structure design
    • 1032. Stream of Characters
    • 745. Prefix and Suffix Search
    • Word Search II
    • 425. Word Squares
    • 642. Design Search Autocomplete System
  • Graph
    • 1192. Critical Connections in a Network
    • 1466. Reorder Routes to Make All Paths Lead to the City Zero
    • 1786. Number of Restricted Paths From First to Last Node
    • 1514. Path with Maximum Probability
    • Bipartition
      • Possible Bipartition
      • Is Graph Bipartite?
  • Union Find
    • 200. Number of Islands
    • 130. Surrounded Regions
    • Friend Circles
    • 947. Most Stones Removed with Same Row or Column
    • Graph Valid Tree
    • 1202. Smallest String With Swaps
    • 721. Accounts Merge
    • Minimize Malware Spread
      • Minimize Malware Spread II
    • Satisfiability of Equality Equations
    • Number of Enclaves
    • 803. Bricks Falling When Hit
    • 685. Redundant Connection II
    • 839. Similar String Groups
    • 305. Number of Islands II
  • Exhaustive Search
    • 78. Subsets
    • 90. Subsets II
    • Permutations
    • Permutations II
    • Partition to K Equal Sum Subsets
      • 216. Combination Sum III
    • 79. Word Search
    • 140. Word Break II
    • 291. Word Pattern II
    • Expression Add Operators
    • Android Unlock Patterns
    • Shopping Offers
    • Binary Watch
    • Generalized Abbreviation
    • 运算
      • Evaluate Division
      • 679. 24 Game
      • 536. Construct Binary Tree from String
      • 736. Parse Lisp Expression
    • 301. Remove Invalid Parentheses
      • 1249. Minimum Remove to Make Valid Parentheses
      • 921. Minimum Add to Make Parentheses Valid
      • 678. Valid Parenthesis String
    • Number of Islands
    • 51. N-Queens
      • 489. Robot Room Cleaner
    • 37. Sudoku Solver
    • 248. Strobogrammatic Number III
    • 1066. Campus Bikes II
    • 691. Stickers to Spell Word
    • 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix
    • 753. Cracking the Safe
    • 1706. Where Will the Ball Fall
    • 465. Optimal Account Balancing
  • String
    • Repeated String Match
    • 13. Roman to Integer
    • String to Integer (atoi)
    • 1451. Rearrange Words in a Sentence
    • Judge Route Circle
    • Remove Comments
    • Count and Say
    • Sentence Screen Fitting
    • Encode and Decode Strings
    • Add Bold Tag in String
    • Group Shifted Strings
    • Valid Word Square
    • 794. Valid Tic-Tac-Toe State
    • 348. Design Tic-Tac-Toe
    • Valid Number
    • Read N Characters Given Read4
      • Read N Characters Given Read4 II - Call multiple times
    • One Edit Distance
    • Restore IP Addresses
    • 468. Validate IP Address
    • 440. K-th Smallest in Lexicographical Order
    • Bold Words in String
    • 1417. Reformat The String
    • 824. Goat Latin
    • License Key Formatting
  • Greedy
    • 1785. Minimum Elements to Add to Form a Given Sum
    • 122. Best Time to Buy and Sell Stock II
    • 45. Jump Game II
    • 55. Jump Game
    • 452. Minimum Number of Arrows to Burst Balloons
    • 871. Minimum Number of Refueling Stops
    • Task Scheduler
    • 768. Max Chunks To Make Sorted II
    • Non-overlapping Intervals
    • 670. Maximum Swap
    • Binary Tree Cameras
    • 135. Candy
    • 358. Rearrange String k Distance Apart
    • 767. Reorganize String
    • 1057. Campus Bikes
    • 936. Stamping The Sequence
    • 1296. Divide Array in Sets of K Consecutive Numbers
    • 1342. Reduce Array Size to The Half
    • 1353. Maximum Number of Events That Can Be Attended
    • 1488. Avoid Flood in The City
    • 1647. Minimum Deletions to Make Character Frequencies Unique
    • 1648. Sell Diminishing-Valued Colored Balls
    • 1665. Minimum Initial Energy to Finish Tasks
  • Design
    • Peeking Iterator
    • Insert Delete GetRandom O(1)
    • Flatten 2D Vector
  • Queue
    • Design Hit Counter
    • 622. Design Circular Queue
    • Moving Average from Data Stream
Powered by GitBook
On this page
  • Thoughts
  • Code
  • Analysis

Was this helpful?

  1. Array & Numbers
  2. 扫描线

The Skyline Problem

Previous扫描线Next253. Meeting Rooms II

Last updated 5 years ago

Was this helpful?

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

Buildings Skyline Contour

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

The number of buildings in any input list is guaranteed to be in the range [0, 10000].

The input list is already sorted in ascending order by the left x position Li.

The output list must be sorted by the x position.

There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]

Thoughts

这题思路是很直观的,遍历并检查每个点最高的高度是否有改变。每个点有什么高度由是由一进一出的范围决定的。扫描线专门用来处理“一进一出”。遍历并track最大自然和heap有关。 难点是多个楼start或end重合时, 先处理谁。当两个点都是start, 我们要只保留高的楼的高度, 因此应先把高楼放进去, 降序排列; 当两个点都是end, 我们要先remove矮楼高度, 因为先删掉高楼高度时当前最高会是矮楼, 而矮楼高度与之前存的最高高度不一样, 因此会把矮楼高度误存进结果。 当两边一进一出时, 应先处理进, 否则先把当前高楼删了后会出现不必要的高度为0的点。

Code

class Solution {
    class Height {
        int height, pos;
        boolean arrive;
        Height(int h, int pos, boolean arrive) {
            this.height = h;
            this.pos = pos;
            this.arrive = arrive;
        }
    }
    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<Height> heights = new ArrayList<>();
        for (int[] b : buildings) {
            heights.add(new Height(b[2], b[0], true));
            heights.add(new Height(b[2], b[1], false));
        }
        Collections.sort(heights, (a, b) -> {
            if (a.pos != b.pos) return a.pos - b.pos;
            if (a.arrive && b.arrive) return b.height - a.height;
            else if (!a.arrive && !b.arrive) return a.height - b.height;
            else return a.arrive ? -1 : 1;
        });
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> (b - a));
        List<List<Integer>> res = new ArrayList<>();
        pq.offer(0);
        int premax = 0;
        for (Height h : heights) {
            if (h.arrive) pq.offer(h.height);
            else pq.remove(h.height);
            if (pq.peek() != premax) {
                List<Integer> r = new ArrayList<>();
                r.add(h.pos);
                r.add(pq.peek());
                res.add(r);
                premax = pq.peek();
            }
        }
        return res;
    }
}

Analysis

排序和建堆时间复杂度O(NlgN).

https://leetcode.com/problems/the-skyline-problem/description/