九章演算法 | Amazon 面試題：The Longest Scene

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

撰文 | JZ

專欄 | 九章演算法

題目描述

一個字元串，每個字元表示一個場景。兩個相同字元之間認為是一個連續的場景。例如:abcda，可以認為這五個字元是同一個場景。或者acafghbeb可以認為又aca和beb兩個場景。場景之間有重合那麼就把場景合起來，例如abcab，這裡abca和bcab是重合的，那麼認為這五個字元是同一個場景。給一個字元串，求最長場景。

思路點撥

首先對於每個字母，我們先找出最長的場景，然後會得到一堆線段，然後將這些線段按照左右端點排序，合併一下即可得到答案。

考點分析

本題整個過程都貫穿著貪心的思想，對於每個字母找出區間很容易想到，在合併區間的時候會有一點小技巧，需要好好斟酌一下，比較考察面試者的思維能力。

九章參考程序

https://www.jiuzhang.com/solution/the-longest-scene/

推薦閱讀：