前往
大廳
主題

LeetCode - 594. Longest Harmonious Subsequence 解題心得

Not In My Back Yard | 2020-12-02 00:00:04 | 巴幣 2 | 人氣 402

題目連結:


題目意譯:
我們定義和諧數列為一數列其滿足其中的最大值與最小值之差值恰好為 1 。

給定一整數陣列 nums ,回傳其所有可能的子序列中最長的和諧子序列之長度。

一個陣列的子序列為一序列,其可藉由從原陣列刪除任意數量元素同時不更動元素之間的相對位置而得來。

限制:
1 ≦ nums.length ≦ 2 × 10 ^ 4
-10 ^ 9 ≦ nums[i] ≦ 10 ^ 9



範例測資:
範例 1:
輸入: nums = [1,3,2,2,5,2,3,7]
輸出: 5
解釋: 最長和諧子序列為 [3,2,2,2,3]。

範例 2:
輸入: nums = [1,2,3,4]
輸出: 2

範例 3:
輸入: nums = [1,1,1,1]
輸出: 0


解題思維:
因為和諧子序列的最大元素與最小元素必定差 1 ,因此將 nums 由小到大排序之後,原本的和諧子序列會重新排列,但因為每個元素最多相差 1,因此會是 nums 的一個連續子序列。

因此,我們只要找出 nums 排序後的最長的和諧連續子序列之長度,就找到了原本 nums 中的最長和諧子序列之長度,即所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作