← 返回目录

解题思路

第 103 / 462 卷日期:

解题思路

设计一个日程类,每添加一个日程,实时显示出当前排期中累计日程最多的个数,例如在一段时间内,排了 3 个日程,其他时间内都只有 0,1,2 个日程,则输出 3。

拿到这个题目以后会立即想到线段树。由于题目中只有增加日程,所以这一题难度不大。这一题和第 699 题也类似,但是有区别,第 699 题中,俄罗斯方块会依次摞起来,而这一题中,俄罗斯方

块也就摞起来,但是方块下面如果是空挡,方块会断掉。举个例子:依次增加区间 [10,20], [10,40],[5,15],[5,10],如果是第 699 题的规则,这 [5,10] 的这块砖块会落在 [5,15] 上,从而使

得高度为 4,但是这一题是日程,日程不一样,[5,15] 这个区间内有 3 个日程,但是其他部分都没有 3 个日程,所以第三块砖块 [5,15] 中的 [5,10] 会“断裂”,掉下去,第四块砖块还是 [5,10],落在

第三块砖块断落下去的位置,它们俩落在一起的高度是 2。

构造一颗线段树,这里用树来构造,如果用数组需要开辟很大的空间。当区间左右边界和查询边界完全相同的时候再累加技术,否则不加,继续划分区间。以区间的左边界作为划分区间的标准,因

为区间左边界是开区间,右边是闭区间。一个区间的计数值以区间左边界的计数为准。还是上面的例子,[5,10) 计数以 5 为标准,count = 2,[10,15) 计数以 10 为标准,count = 3。还需要再动态

维护一个最大值。这个线段树的实现比较简单。

类似的题目有:第 715 题,第 218 题,第 699 题。第 715 题是区间更新定值(不是增减),第 218 题可以用扫描线,第 732 题和第 699 题类似,也是俄罗斯方块的题目,但是第 732 题的俄罗斯方

块的方块会“断裂”。

代码

package leetcode

// SegmentTree732 define type SegmentTree732 struct {

start, end, count int left, right*SegmentTree732

}

// MyCalendarThree define type MyCalendarThree struct {

st*SegmentTree732 maxHeight int

}

// Constructor732 define func Constructor732() MyCalendarThree {

st := &SegmentTree732{ start: 0,

end:1e9,

// Book define func (mct *MyCalendarThree) Book(start int, end int) int {

mct.st.book(start, end, &mct.maxHeight)

return mct.maxHeight }

func (st *SegmentTree732) book(start, end int, maxHeight *int) { if start == end {

return }

if start == st.start && st.end == end { st.count++

if st.count > *maxHeight { *maxHeight = st.count

} if st.left == nil {

return }

} if st.left == nil {

if start == st.start { st.left = &SegmentTree732{start: start, end: end, count: st.count}

st.right = &SegmentTree732{start: end, end: st.end, count: st.count} st.left.book(start, end, maxHeight)

return }

st.left = &SegmentTree732{start: st.start, end: start, count: st.count} st.right = &SegmentTree732{start: start, end: st.end, count: st.count}

st.right.book(start, end, maxHeight)

return }

if start >= st.right.start { st.right.book(start, end, maxHeight)

} else if end <= st.left.end { st.left.book(start, end, maxHeight)

} else { st.left.book(start, st.left.end, maxHeight)

st.right.book(st.right.start, end, maxHeight)

} }

/**

  • Your MyCalendarThree object will be instantiated and called as such:
  • obj := Constructor();
全站分卷索引 · 462 卷
  1. 1532. K-diff Pairs in an Array
  2. 2题目大意
  3. 3537. Complex Number Multiplication
  4. 4541. Reverse String II
  5. 5解题思路
  6. 6题目大意
  7. 7代码
  8. 8547. Friend Circles
  9. 9解题思路
  10. 10557. Reverse Words in a String III
  11. 11代码
  12. 12题目大意
  13. 13题目
  14. 14566. Reshape the Matrix
  15. 15题目大意
  16. 16代码
  17. 17题目大意
  18. 18572. Subtree of Another Tree
  19. 19题目大意
  20. 20575. Distribute Candies
  21. 21题目大意
  22. 22解题思路
  23. 23题目大意
  24. 24代码
  25. 25题目大意
  26. 26628. Maximum Product of Three Numbers
  27. 27632. Smallest Range Covering Elements from K Lists
  28. 28代码
  29. 29633. Sum of Square Numbers
  30. 30解题思路
  31. 31题目大意
  32. 32代码
  33. 33637. Average of Levels in Binary Tree
  34. 34638. Shopping Offers
  35. 35题目大意
  36. 36解题思路
  37. 37645. Set Mismatch
  38. 38题目大意
  39. 39648. Replace Words
  40. 40653. Two Sum IV - Input is a BST
  41. 41题目大意
  42. 42题目大意
  43. 43代码
  44. 44题目大意
  45. 45662. Maximum Width of Binary Tree
  46. 46题目大意
  47. 47代码
  48. 48668. Kth Smallest Number in Multiplication Table
  49. 49题目大意
  50. 50676. Implement Magic Dictionary
  51. 51题目大意
  52. 52682. Baseball Game
  53. 53题目大意
  54. 54684. Redundant Connection
  55. 55题目大意
  56. 56解题思路
  57. 57题目大意
  58. 58代码
  59. 59693. Binary Number with Alternating Bits
  60. 60题目大意
  61. 61695. Max Area of Island
  62. 62题目大意
  63. 63697. Degree of an Array
  64. 64代码
  65. 65题目大意
  66. 66解题思路
  67. 67代码
  68. 68704. Binary Search
  69. 69代码
  70. 70题目大意
  71. 71706. Design HashMap
  72. 72题目大意
  73. 73707. Design Linked List
  74. 74题目大意
  75. 75710. Random Pick with Blacklist
  76. 76题目大意
  77. 77代码
  78. 78713. Subarray Product Less Than K
  79. 79代码
  80. 80题目大意
  81. 81715. Range Module
  82. 82题目大意
  83. 83717. 1-bit and 2-bit Characters
  84. 84题目大意
  85. 85题目大意
  86. 86719. Find K-th Smallest Pair Distance
  87. 87题目大意
  88. 88720. Longest Word in Dictionary
  89. 89题目大意
  90. 90721. Accounts Merge
  91. 91题目大意
  92. 92代码
  93. 93725. Split Linked List in Parts
  94. 94题目大意
  95. 95726. Number of Atoms
  96. 96题目大意
  97. 97解题思路
  98. 98729. My Calendar I
  99. 99题目大意
  100. 100解题思路
  101. 101732. My Calendar III
  102. 102题目大意
  103. 103解题思路
  104. 104733. Flood Fill
  105. 105解题思路
  106. 106题目
  107. 107题目大意
  108. 108739. Daily Temperatures
  109. 109744. Find Smallest Letter Greater Than Target
  110. 110题目大意
  111. 111745. Prefix and Suffix Search
  112. 112解题思路
  113. 113746. Min Cost Climbing Stairs
  114. 114题目大意
  115. 115748. Shortest Completing Word
  116. 116题目大意
  117. 117753. Cracking the Safe
  118. 118题目大意
  119. 119756. Pyramid Transition Matrix
  120. 120题目大意
  121. 121代码
  122. 122题目大意
  123. 123763. Partition Labels
  124. 124解题思路
  125. 125765. Couples Holding Hands
  126. 126题目大意
  127. 127代码
  128. 128题目大意
  129. 129767. Reorganize String
  130. 130代码
  131. 131771. Jewels and Stones
  132. 132代码
  133. 133题目大意
  134. 134代码
  135. 135781. Rabbits in Forest
  136. 136题目大意
  137. 137784. Letter Case Permutation
  138. 138786. K-th Smallest Prime Fraction
  139. 139题目大意
  140. 140793. Preimage Size of Factorial Zeroes Function
  141. 141解题思路
  142. 142代码
  143. 143802. Find Eventual Safe States
  144. 144解题思路
  145. 145题目大意
  146. 146解题思路
  147. 147811. Subdomain Visit Count
  148. 148题目
  149. 149解题思路
  150. 150812. Largest Triangle Area
  151. 151题目大意
  152. 152815. Bus Routes
  153. 153代码
  154. 154817. Linked List Components
  155. 155解题思路
  156. 156819. Most Common Word
  157. 157题目大意
  158. 158826. Most Profit Assigning Work
  159. 159代码
  160. 160828. Unique Letter String
  161. 161代码
  162. 162832. Flipping an Image
  163. 163题目大意
  164. 164题目大意
  165. 165836. Rectangle Overlap
  166. 166解题思路
  167. 167题目大意
  168. 168839. Similar String Groups
  169. 169题目大意
  170. 170841. Keys and Rooms
  171. 171题目大意
  172. 172842. Split Array into Fibonacci Sequence
  173. 173题目大意
  174. 174844. Backspace String Compare
  175. 175题目大意
  176. 176845. Longest Mountain in Array
  177. 177题目大意
  178. 178850. Rectangle Area II
  179. 179题目大意
  180. 180代码
  181. 181851. Loud and Rich
  182. 182题目大意
  183. 183解题思路
  184. 184852. Peak Index in a Mountain Array
  185. 185解题思路
  186. 186853. Car Fleet
  187. 187题目大意
  188. 188856. Score of Parentheses
  189. 189题目大意
  190. 190862. Shortest Subarray with Sum at Least K
  191. 191题目大意
  192. 192863. All Nodes Distance K in Binary Tree
  193. 193题目大意
  194. 194代码
  195. 195864. Shortest Path to Get All Keys
  196. 196解题思路
  197. 197867. Transpose Matrix
  198. 198872. Leaf-Similar Trees
  199. 199题目大意
  200. 200代码
  201. 201题目大意
  202. 202876. Middle of the Linked List
  203. 203题目大意
  204. 204878. Nth Magical Number
  205. 205题目大意
  206. 206880. Decoded String at Index
  207. 207题目大意
  208. 208881. Boats to Save People
  209. 209解题思路
  210. 210题目大意
  211. 211885. Spiral Matrix III
  212. 212题目大意
  213. 213887. Super Egg Drop
  214. 214题目大意
  215. 215代码
  216. 216题目
  217. 217解题思路
  218. 218891. Sum of Subsequence Widths
  219. 219代码
  220. 220题目大意
  221. 221895. Maximum Frequency Stack
  222. 222题目大意
  223. 223解题思路
  224. 224896. Monotonic Array
  225. 225题目大意
  226. 226897. Increasing Order Search Tree
  227. 227解题思路
  228. 228898. Bitwise ORs of Subarrays
  229. 229题目大意
  230. 230代码
  231. 231901. Online Stock Span
  232. 232题目大意
  233. 233904. Fruit Into Baskets
  234. 234题目大意
  235. 235907. Sum of Subarray Minimums
  236. 236代码
  237. 237911. Online Election
  238. 238解题思路
  239. 239914. X of a Kind in a Deck of Cards
  240. 240题目大意
  241. 241918. Maximum Sum Circular Subarray
  242. 242题目大意
  243. 243代码
  244. 244题目大意
  245. 245代码
  246. 246921. Minimum Add to Make Parentheses Valid
  247. 247题目大意
  248. 248题目大意
  249. 249题目
  250. 250924. Minimize Malware Spread
  251. 251题目大意
  252. 252解题思路
  253. 253925. Long Pressed Name
  254. 254题目大意
  255. 255927. Three Equal Parts
  256. 256题目大意
  257. 257928. Minimize Malware Spread II
  258. 258题目大意
  259. 259解题思路
  260. 260930. Binary Subarrays With Sum
  261. 261代码
  262. 262题目大意
  263. 263942. DI String Match
  264. 264代码
  265. 265题目大意
  266. 266题目
  267. 267代码
  268. 268题目大意
  269. 269952. Largest Component Size by Common Factor
  270. 270题目大意
  271. 271代码
  272. 272953. Verifying an Alien Dictionary
  273. 273题目大意
  274. 274959. Regions Cut By Slashes
  275. 275题目大意
  276. 276代码
  277. 277961. N-Repeated Element in Size 2N Array
  278. 278代码
  279. 279题目大意
  280. 280代码
  281. 281969. Pancake Sorting
  282. 282题目大意
  283. 283970. Powerful Integers
  284. 284题目大意
  285. 285973. K Closest Points to Origin
  286. 286题目大意
  287. 287976. Largest Perimeter Triangle
  288. 288题目大意
  289. 289题目大意
  290. 290978. Longest Turbulent Subarray
  291. 291题目大意
  292. 292979. Distribute Coins in Binary Tree
  293. 293题目大意
  294. 294代码
  295. 295980. Unique Paths III
  296. 296题目大意
  297. 297981. Time Based Key-Value Store
  298. 298题目大意
  299. 299解题思路
  300. 300984. String Without AAA or BBB
  301. 301题目大意
  302. 302985. Sum of Even Numbers After Queries
  303. 303题目大意
  304. 304986. Interval List Intersections
  305. 305代码
  306. 306题目大意
  307. 307解题思路
  308. 308题目
  309. 309代码
  310. 310993. Cousins in Binary Tree
  311. 311题目大意
  312. 312解题思路
  313. 313995. Minimum Number of K Consecutive Bit Flips
  314. 314题目大意
  315. 315代码
  316. 316996. Number of Squareful Arrays
  317. 317代码
  318. 318999. Available Captures for Rook
  319. 319题目大意
  320. 320解题思路
  321. 3211002. Find Common Characters
  322. 3221003. Check If Word Is Valid After Substitutions
  323. 323题目大意
  324. 324解题思路
  325. 3251004. Max Consecutive Ones III
  326. 3261005. Maximize Sum Of Array After K Negations
  327. 327题目大意
  328. 3281011. Capacity To Ship Packages Within D Days
  329. 329题目大意
  330. 3301017. Convert to Base -2
  331. 331解题思路
  332. 332题目大意
  333. 3331020. Number of Enclaves
  334. 334题目大意
  335. 3351021. Remove Outermost Parentheses
  336. 336题目大意
  337. 337代码
  338. 3381025. Divisor Game
  339. 339代码
  340. 340题目大意
  341. 341解题思路
  342. 342题目大意
  343. 343解题思路
  344. 3441030. Matrix Cells in Distance Order
  345. 345题目大意
  346. 346代码
  347. 347题目大意
  348. 348题目大意
  349. 349代码
  350. 3501047. Remove All Adjacent Duplicates In String
  351. 351题目大意
  352. 3521049. Last Stone Weight II
  353. 353代码
  354. 354题目大意
  355. 3551052. Grumpy Bookstore Owner
  356. 356解题思路
  357. 3571054. Distant Barcodes
  358. 358题目大意
  359. 3591073. Adding Two Negabinary Numbers
  360. 360题目大意
  361. 361代码
  362. 3621074. Number of Submatrices That Sum to Target
  363. 363解题思路
  364. 3641078. Occurrences After Bigram
  365. 365解题思路
  366. 366题目大意
  367. 3671089. Duplicate Zeros
  368. 3681093. Statistics from a Large Sample
  369. 369题目大意
  370. 3701105. Filling Bookcase Shelves
  371. 371题目大意
  372. 3721108. Defanging an IP Address
  373. 373代码
  374. 374题目大意
  375. 3751111. Maximum Nesting Depth of Two Valid Parentheses Strings
  376. 376题目大意
  377. 377代码
  378. 3781122. Relative Sort Array
  379. 379解题思路
  380. 3801123. Lowest Common Ancestor of Deepest Leaves
  381. 381题目大意
  382. 3821128. Number of Equivalent Domino Pairs
  383. 383解题思路
  384. 384题目大意
  385. 3851145. Binary Tree Coloring Game
  386. 386题目大意
  387. 387解题思路
  388. 3881154. Day of the Year
  389. 389题目大意
  390. 390题目
  391. 391解题思路
  392. 392代码
  393. 3931160. Find Words That Can Be Formed by Characters
  394. 394解题思路
  395. 395题目大意
  396. 396代码
  397. 397题目大意
  398. 3981175. Prime Arrangements
  399. 399题目大意
  400. 4001184. Distance Between Bus Stops
  401. 401题目大意
  402. 402解题思路
  403. 403题目大意
  404. 404题目
  405. 405代码
  406. 406题目大意
  407. 4071201. Ugly Number III
  408. 408解题思路
  409. 409题目大意
  410. 410解题思路
  411. 4111207. Unique Number of Occurrences
  412. 4121208. Get Equal Substrings Within Budget
  413. 413题目大意
  414. 4141217. Play with Chips
  415. 415题目大意
  416. 416题目
  417. 417代码
  418. 418题目大意
  419. 419解题思路
  420. 420题目大意
  421. 421代码
  422. 422题目大意
  423. 4231252. Cells with Odd Values in a Matrix
  424. 424题目大意
  425. 425解题思路
  426. 4261254. Number of Closed Islands
  427. 427题目大意
  428. 4281260. Shift 2D Grid
  429. 429题目大意
  430. 430代码
  431. 431题目大意
  432. 432题目大意
  433. 433代码
  434. 4341281. Subtract the Product and Sum of Digits of an Integer
  435. 4351283. Find the Smallest Divisor Given a Threshold
  436. 436题目大意
  437. 4371287. Element Appearing More Than 25% In Sorted Array
  438. 4381290. Convert Binary Number in a Linked List to Integer
  439. 439题目大意
  440. 440题目大意
  441. 4411299. Replace Elements with Greatest Element on Right Side
  442. 4421300. Sum of Mutated Array Closest to Target
  443. 443解题思路
  444. 4441302. Deepest Leaves Sum
  445. 4451304. Find N Unique Integers Sum up to Zero
  446. 446解题思路
  447. 447题目大意
  448. 448解题思路
  449. 449题目大意
  450. 4501313. Decompress Run-Length Encoded List
  451. 451解题思路
  452. 452题目大意
  453. 4531380. Lucky Numbers in a Matrix
  454. 454题目大意
  455. 4551385. Find the Distance Value Between Two Arrays
  456. 456题目大意
  457. 4571389. Create Target Array in the Given Order
  458. 458题目大意
  459. 459题目大意
  460. 460题目大意
  461. 4611470. Shuffle the Array
  462. 462解题思路