九章演算法 | Facebook 面試題：Digital Coverage

來自專欄九章演算法 - lintcode/leetcode題解

撰文 | JZ

專欄 | 九章演算法

題目描述

給出一些區間，問覆蓋次數最多的數是多少，如果有多個，輸出最小的那個數。

思路點撥

由於只查詢一次，故可以使用前綴和的方式來記錄區間的覆蓋範圍，然後O(n)掃一次，整體複雜度O(n)。

考點分析

本題用到一個小技巧，對於一段區間[start, end]加上一個數c，可以f[start] += c, f[end + 1] -= c, 這樣再求前綴和，就能達到想要的效果。

九章參考程序

https://www.jiuzhang.com/solution/digital-coverage/

推薦閱讀：