代码
到一个大楼的左边界,有比它更高的高度,就不记录,因为它不是天际线,它被楼挡楼,挡在其他楼后面了。当扫到一个大楼的右边界的时候,如果是最高点,那么记录下它的状态是离开状态,此
时还需要记录下第二高的点。在扫描线扫描的过程中,动态的维护大楼的高度,同时维护最高的高度和第二高的高度。其实只需要维护最高的高度这一个高度,因为当离开状态到来的时候,移除掉
当前最高的,剩下的高度里面最高的就是第二高的高度。描述的伪代码如下:
// 扫描线伪代码 events = {{x: L , height: H , type: entering},
{x: R , height: H , type: leaving}} event.SortByX()
ds = new DS()
for e in events:
if entering(e):
if e.height > ds.max(): ans += [e.height] ds.add(e.height)
if leaving(e):
ds.remove(e.height)
if e.height > ds.max(): ans += [ds.max()]
动态插入,查找最大值可以选用的数据结构有,最大堆和二叉搜索树。最大堆找最大值 O(1),插入 O(log n),但是 remove_by_key 需要 O(n) 的时间复杂度,并且需要自己实现。二叉搜索树,
查找 max,添加和删除元素都是 O(log n) 的时间复杂度。
排序的时候也需要注意几个问题:如果大楼的边界相等,并且是进入状态,那么再按照高度从大到小进行排序;如果大楼的边界相等,并且是离开状态,那么高度按照从小到大进行排序。
代码
package leetcode
import ( "sort"
"github.com/halfrost/LeetCode-Go/template"
)
// 解法一线段树 Segment Tree,时间复杂度 O(n log n)
func getSkyline(buildings [][]int) [][]int { st, ans, lastHeight, check := template.SegmentTree{}, [][]int{}, 0, false
posMap, pos := discretization218(buildings)
tmp := make([]int, len(posMap))
st.Init(tmp, func(i, j int) int {
} for i := 0; i < len(pos); i++ {
h := st.QueryLazy(posMap[pos[i]], posMap[pos[i]])
if check == false && h != 0 { ans = append(ans, []int{pos[i], h})
check = true } else if i > 0 && h != lastHeight {
ans = append(ans, []int{pos[i], h})
} lastHeight = h
} return ans
}
func discretization218(positions [][]int) (map[int]int, []int) { tmpMap, posArray, posMap := map[int]int{}, []int{}, map[int]int{}
for _, pos := range positions { tmpMap[pos[0]]++
tmpMap[pos[1]-1]++ tmpMap[pos[1]]++
} for k := range tmpMap {
posArray = append(posArray, k)
} sort.Ints(posArray)
for i, pos := range posArray { posMap[pos] = i
} return posMap, posArray
}
// 解法二扫描线 Sweep Line,时间复杂度 O(n log n)
func getSkyline1(buildings [][]int) [][]int { size := len(buildings)
es := make([]E, 0)
for i, b := range buildings { l := b[0]
r := b[1] h := b[2]
// 1-- enter el := NewE(i, l, h, 0)
es = append(es, el)
// 0 -- leave er := NewE(i, r, h, 1)
es = append(es, er)
if es[i].T == es[j].T { if es[i].T == 0 {
return es[i].H > es[j].H }
return es[i].H < es[j].H }
return es[i].T < es[j].T }
return es[i].X < es[j].X })
pq := NewIndexMaxPQ(size)
for _, e := range es { curH := pq.Front()
if e.T == 0 { if e.H > curH {
skyline = append(skyline, []int{e.X, e.H})
} pq.Enque(e.N, e.H)
} else { pq.Remove(e.N)
h := pq.Front()
if curH > h { skyline = append(skyline, []int{e.X, h})
} }
} return skyline
}
// 扫面线伪代码 // events = {{x: L , height: H , type: entering},
//{x: R , height: H , type: leaving}} // event.SortByX()
// ds = new DS()
// for e in events:
//if entering(e):
| // | ife.height>ds.max():ans+=[e.height] |
|---|---|
| // | ds.add(e.height) |
| // | ifleaving(e): |
| // | ds.remove(e.height) |
| // | ife.height>ds.max():ans+=[ds.max()] |
// E define type E struct { // 定义一个 event 事件
}
// NewE define func NewE(n, x, h, t int) E {
return E{ N: n,
X: x, H: h,
T: t, }
}
// IndexMaxPQ define type IndexMaxPQ struct {
items []int pq[]int
qp[]int total int
}
// NewIndexMaxPQ define func NewIndexMaxPQ(n int) IndexMaxPQ {
qp := make([]int, n)
for i := 0; i < n; i++ { qp[i] = -1
} return IndexMaxPQ{
items: make([]int, n), pq:make([]int, n+1),
qp:qp, }
}
// Enque define func (q *IndexMaxPQ) Enque(key, val int) {
q.total++ q.items[key] = val
q.pq[q.total] = key q.qp[key] = q.total
q.swim(q.total)
}
// Front define func (q *IndexMaxPQ) Front() int {
if q.total < 1 {
// Remove define func (q *IndexMaxPQ) Remove(key int) {
rank := q.qp[key] q.exch(rank, q.total)
q.total-- q.qp[key] = -1
q.sink(rank)
}
func (q *IndexMaxPQ) sink(n int) { for 2*n <= q.total {
k := 2 * n if k < q.total && q.less(k, k+1) {
k++ }
if q.less(k, n) { break
} q.exch(k, n)
n = k }
}
func (q *IndexMaxPQ) swim(n int) { for n > 1 {
k := n / 2 if q.less(n, k) {
break }
q.exch(n, k)
n = k }
}
func (q *IndexMaxPQ) exch(i, j int) { q.pq[i], q.pq[j] = q.pq[j], q.pq[i]
q.qp[q.pq[i]] = i q.qp[q.pq[j]] = j
}
func (q *IndexMaxPQ) less(i, j int) bool { return q.items[q.pq[i]] < q.items[q.pq[j]]
219. Contains Duplicate II
全站分卷索引 · 484 卷
- 1关于书的封面
- 2目标读者
- 3第二章 算法专题
- 4Array
- 5Backtracking
- 6Binary Indexed Tree
- 7Bit Manipulation
- 8Breadth First Search
- 9Depth First Search
- 10Dynamic Programming
- 11Hash Table
- 12Linked List
- 13Math
- 14Segment Tree
- 15Sliding Window
- 16Sort
- 17Stack
- 18String
- 19Tree
- 20Two Pointers
- 21Union Find
- 22第三章 一些模板
- 23并查集 UnionFind
- 24第四章 Leetcode 题解
- 251. Two Sum
- 26题目大意
- 27题目大意
- 283. Longest Substring Without Repeating Characters
- 29题目大意
- 304. Median of Two Sorted Arrays
- 31题目大意
- 32代码
- 337. Reverse Integer
- 34解题思路
- 35题目大意
- 3611. Container With Most Water
- 3713. Roman to Integer
- 38题目大意
- 39解题思路
- 4015. 3Sum
- 41代码
- 42题目
- 4317. Letter Combinations of a Phone Number
- 44题目大意
- 4518. 4Sum
- 46题目大意
- 4719. Remove Nth Node From End of List
- 4820. Valid Parentheses
- 49题目大意
- 50题目大意
- 51题目
- 5223. Merge k Sorted Lists
- 5324. Swap Nodes in Pairs
- 54解题思路
- 5525. Reverse Nodes in k-Group
- 5626. Remove Duplicates from Sorted Array
- 57题目大意
- 5827. Remove Element
- 59题目大意
- 6028. Implement strStr()
- 6129. Divide Two Integers
- 62题目大意
- 6330. Substring with Concatenation of All Words
- 6433. Search in Rotated Sorted Array
- 65代码
- 66题目
- 6735. Search Insert Position
- 68题目大意
- 69题目大意
- 7037. Sudoku Solver
- 71题目大意
- 72代码
- 7339. Combination Sum
- 74题目大意
- 7540. Combination Sum II
- 76解题思路
- 7741. First Missing Positive
- 7842. Trapping Rain Water
- 79代码
- 8046. Permutations
- 8147. Permutations II
- 82解题思路
- 8348. Rotate Image
- 84解题思路
- 8549. Group Anagrams
- 86题目大意
- 8750. Pow(x, n)
- 8851. N-Queens
- 89题目大意
- 9052. N-Queens II
- 91题目大意
- 9253. Maximum Subarray
- 9354. Spiral Matrix
- 94题目大意
- 9555. Jump Game
- 9656. Merge Intervals
- 9757. Insert Interval
- 98解题思路
- 9959. Spiral Matrix II
- 10060. Permutation Sequence
- 101题目大意
- 10261. Rotate List
- 103题目大意
- 10462. Unique Paths
- 105题目大意
- 10663. Unique Paths II
- 107解题思路
- 108题目大意
- 10966. Plus One
- 110题目大意
- 11167. Add Binary
- 11269. Sqrt(x)
- 113题目大意
- 114代码
- 11570. Climbing Stairs
- 116题目大意
- 117题目大意
- 11874. Search a 2D Matrix
- 119解题思路
- 120题目大意
- 12176. Minimum Window Substring
- 12277. Combinations
- 123题目大意
- 12478. Subsets
- 12579. Word Search
- 12680. Remove Duplicates from Sorted Array II
- 127题目大意
- 12881. Search in Rotated Sorted Array II
- 129解题思路
- 13082. Remove Duplicates from Sorted List II
- 13183. Remove Duplicates from Sorted List
- 13284. Largest Rectangle in Histogram
- 133题目大意
- 13486. Partition List
- 135代码
- 13688. Merge Sorted Array
- 137题目大意
- 13889. Gray Code
- 139代码
- 14090. Subsets II
- 141解题思路
- 14291. Decode Ways
- 143代码
- 144题目大意
- 14593. Restore IP Addresses
- 14694. Binary Tree Inorder Traversal
- 147题目大意
- 14895. Unique Binary Search Trees II
- 14996. Unique Binary Search Trees
- 150题目大意
- 15198. Validate Binary Search Tree
- 15299. Recover Binary Search Tree
- 153题目大意
- 154100. Same Tree
- 155题目大意
- 156101. Symmetric Tree
- 157102. Binary Tree Level Order Traversal
- 158解题思路
- 159103. Binary Tree Zigzag Level Order Traversal
- 160题目大意
- 161104. Maximum Depth of Binary Tree
- 162题目大意
- 163题目大意
- 164106. Construct Binary Tree from Inorder and Postorder Traversal
- 165解题思路
- 166题目大意
- 167108. Convert Sorted Array to Binary Search Tree
- 168109. Convert Sorted List to Binary Search Tree
- 169解题思路
- 170110. Balanced Binary Tree
- 171题目大意
- 172111. Minimum Depth of Binary Tree
- 173112. Path Sum
- 174代码
- 175题目大意
- 176114. Flatten Binary Tree to Linked List
- 177题目大意
- 178代码
- 179120. Triangle
- 180121. Best Time to Buy and Sell Stock
- 181题目大意
- 182122. Best Time to Buy and Sell Stock II
- 183题目大意
- 184题目
- 185125. Valid Palindrome
- 186题目大意
- 187126. Word Ladder II
- 188题目大意
- 189127. Word Ladder
- 190题目大意
- 191解题思路
- 192128. Longest Consecutive Sequence
- 193代码
- 194129. Sum Root to Leaf Numbers
- 195题目大意
- 196130. Surrounded Regions
- 197题目大意
- 198131. Palindrome Partitioning
- 199136. Single Number
- 200题目大意
- 201题目大意
- 202代码
- 203141. Linked List Cycle
- 204代码
- 205143. Reorder List
- 206代码
- 207144. Binary Tree Preorder Traversal
- 208题目
- 209145. Binary Tree Postorder Traversal
- 210147. Insertion Sort List
- 211题目大意
- 212148. Sort List
- 213150. Evaluate Reverse Polish Notation
- 214题目大意
- 215151. Reverse Words in a String
- 216题目大意
- 217题目
- 218153. Find Minimum in Rotated Sorted Array
- 219154. Find Minimum in Rotated Sorted Array II
- 220解题思路
- 221题目大意
- 222160. Intersection of Two Linked Lists
- 223题目大意
- 224162. Find Peak Element
- 225题目大意
- 226164. Maximum Gap
- 227题目大意
- 228167. Two Sum II - Input array is sorted
- 229题目大意
- 230168. Excel Sheet Column Title
- 231解题思路
- 232题目大意
- 233171. Excel Sheet Column Number
- 234172. Factorial Trailing Zeroes
- 235代码
- 236题目大意
- 237174. Dungeon Game
- 238题目大意
- 239代码
- 240179. Largest Number
- 241题目大意
- 242187. Repeated DNA Sequences
- 243题目大意
- 244190. Reverse Bits
- 245题目大意
- 246题目大意
- 247198. House Robber
- 248解题思路
- 249199. Binary Tree Right Side View
- 250代码
- 251200. Number of Islands
- 252201. Bitwise AND of Numbers Range
- 253题目大意
- 254202. Happy Number
- 255代码
- 256解题思路
- 257题目大意
- 258题目大意
- 259206. Reverse Linked List
- 260207. Course Schedule
- 261题目大意
- 262208. Implement Trie (Prefix Tree)
- 263209. Minimum Size Subarray Sum
- 264210. Course Schedule II
- 265题目大意
- 266211. Add and Search Word - Data structure design
- 267解题思路
- 268212. Word Search II
- 269题目大意
- 270题目大意
- 271215. Kth Largest Element in an Array
- 272代码
- 273题目大意
- 274217. Contains Duplicate
- 275题目大意
- 276题目大意
- 277代码
- 278219. Contains Duplicate II
- 279220. Contains Duplicate III
- 280解题思路
- 281222. Count Complete Tree Nodes
- 282题目大意
- 283223. Rectangle Area
- 284题目大意
- 285题目大意
- 286225. Implement Stack using Queues
- 287题目
- 288226. Invert Binary Tree
- 289题目大意
- 290229. Majority Element II
- 291230. Kth Smallest Element in a BST
- 292题目大意
- 293题目大意
- 294232. Implement Queue using Stacks
- 295题目大意
- 296234. Palindrome Linked List
- 297题目大意
- 298235. Lowest Common Ancestor of a Binary Search Tree
- 299题目大意
- 300代码
- 301题目大意
- 302237. Delete Node in a Linked List
- 303解题思路
- 304题目大意
- 305240. Search a 2D Matrix II
- 306题目大意
- 307242. Valid Anagram
- 308题目大意
- 309257. Binary Tree Paths
- 310258. Add Digits
- 311260. Single Number III
- 312代码
- 313题目大意
- 314题目大意
- 315题目大意
- 316275. H-Index II
- 317题目大意
- 318283. Move Zeroes
- 319287. Find the Duplicate Number
- 320解题思路
- 321290. Word Pattern
- 322题目大意
- 323300. Longest Increasing Subsequence
- 324解题思路
- 325303. Range Sum Query - Immutable
- 326解题思路
- 327306. Additive Number
- 328题目大意
- 329307. Range Sum Query - Mutable
- 330解题思路
- 331309. Best Time to Buy and Sell Stock with Cooldown
- 332题目大意
- 333代码
- 334315. Count of Smaller Numbers After Self
- 335318. Maximum Product of Word Lengths
- 336题目大意
- 337322. Coin Change
- 338题目大意
- 339题目大意
- 340代码
- 341326. Power of Three
- 342题目大意
- 343327. Count of Range Sum
- 344解题思路
- 345代码
- 346328. Odd Even Linked List
- 347题目大意
- 348329. Longest Increasing Path in a Matrix
- 349题目大意
- 350331. Verify Preorder Serialization of a Binary Tree
- 351题目大意
- 352337. House Robber III
- 353题目大意
- 354338. Counting Bits
- 355342. Power of Four
- 356343. Integer Break
- 357代码
- 358题目大意
- 359题目大意
- 360347. Top K Frequent Elements
- 361349. Intersection of Two Arrays
- 362350. Intersection of Two Arrays II
- 363代码
- 364解题思路
- 365357. Count Numbers with Unique Digits
- 366代码
- 367题目大意
- 368题目大意
- 369题目大意
- 370373. Find K Pairs with Smallest Sums
- 371解题思路
- 372378. Kth Smallest Element in a Sorted Matrix
- 373代码
- 374385. Mini Parser
- 375题目大意
- 376386. Lexicographical Numbers
- 377387. First Unique Character in a String
- 378389. Find the Difference
- 379392. Is Subsequence
- 380解题思路
- 381题目
- 382解题思路
- 383394. Decode String
- 384397. Integer Replacement
- 385题目大意
- 386代码
- 387题目大意
- 388代码
- 389401. Binary Watch
- 390题目大意
- 391解题思路
- 392402. Remove K Digits
- 393题目大意
- 394题目大意
- 395题目
- 396代码
- 397题目大意
- 398题目大意
- 399412. Fizz Buzz
- 400题目大意
- 401414. Third Maximum Number
- 402解题思路
- 403题目大意
- 404421. Maximum XOR of Two Numbers in an Array
- 405代码
- 406424. Longest Repeating Character Replacement
- 407题目大意
- 408433. Minimum Genetic Mutation
- 409题目大意
- 410435. Non-overlapping Intervals
- 411题目大意
- 412436. Find Right Interval
- 413题目大意
- 414437. Path Sum III
- 415代码
- 416题目大意
- 417代码
- 418441. Arranging Coins
- 419代码
- 420解题思路
- 421447. Number of Boomerangs
- 422题目大意
- 423448. Find All Numbers Disappeared in an Array
- 424451. Sort Characters By Frequency
- 425题目大意
- 426453. Minimum Moves to Equal Array Elements
- 427题目大意
- 428题目大意
- 429455. Assign Cookies
- 430题目大意
- 431题目大意
- 432457. Circular Array Loop
- 433题目大意
- 434461. Hamming Distance
- 435题目大意
- 436题目大意
- 437470. Implement Rand10() Using Rand7()
- 438题目大意
- 439代码
- 440题目大意
- 441475. Heaters
- 442题目大意
- 443476. Number Complement
- 444477. Total Hamming Distance
- 445解题思路
- 446题目大意
- 447代码
- 448483. Smallest Good Base
- 449题目大意
- 450代码
- 451485. Max Consecutive Ones
- 452代码
- 453解题思路
- 454493. Reverse Pairs
- 455代码
- 456494. Target Sum
- 457代码
- 458496. Next Greater Element I
- 459题目大意
- 460497. Random Point in Non-overlapping Rectangles
- 461解题思路
- 462498. Diagonal Traverse
- 463题目大意
- 464解题思路
- 465500. Keyboard Row
- 466题目大意
- 467题目
- 468507. Perfect Number
- 469题目大意
- 470508. Most Frequent Subtree Sum
- 471509. Fibonacci Number
- 472题目大意
- 473513. Find Bottom Left Tree Value
- 474解题思路
- 475515. Find Largest Value in Each Tree Row
- 476524. Longest Word in Dictionary through Deleting
- 477代码
- 478题目大意
- 479528. Random Pick with Weight
- 480题目大意
- 481代码
- 482529. Minesweeper
- 483题目大意
- 484解题思路