go語言題解LeetCode674最長連續遞增序列
題目描述
674. 最長連續遞增序列
給定一個未經排序的整數數組,找到最長且 連續遞增的子序列,並返回該序列的長度。
連續遞增的子序列 可以由兩個下標 l
和 r(l < r)
確定,如果對於每個 l <= i < r
,都有 nums[i] < nums[i + 1]
,那麼子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]]
就是連續遞增子序列。
示例 1:
輸入:nums = [1,3,5,4,7] 輸出:3 解釋:最長連續遞增序列是 [1,3,5], 長度為3。 盡管 [1,3,5,7] 也是升序的子序列, 但它不是連續的,因為 5 和 7 在原數組裡被 4 隔開。
示例 2:
輸入:nums = [2,2,2,2,2] 輸出:1 解釋:最長連續遞增序列是 [2], 長度為1。
提示:
1 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
思路分析
一次遍歷:
維護一個記錄當前遞增的長度的數值:temp = 1,因為最少的遞增長度也為 1
更新temp:
- 當前數值 大於 之前的數值時, 為遞增序列,temp = temp + 1
- 當前數值 小於或等於 之前的數值時,將 temp 歸入到結果列表中,重置 temp = 1
當結束時,將最後的 temp 歸入到結果列表中
返回結果列表中最大的值。
當然也可以不使用列表存儲,隻需要再重置 temp 之前,比較當前的 temp 和 最大的 temp_max,然後更新 temp_max 即可。使用 列表更加有助於理解。
AC 代碼
class Solution: def findLengthOfLCIS(self, nums: List[int]) -> int: rev = [] ln = len(nums) if ln == 0 or ln == 1: return ln temp = 1 for i in range(1, ln): if nums[i]>nums[i-1]: temp += 1 else: rev.append(temp) temp = 1 rev.append(temp) return max(rev)
不使用列表:
class Solution: def findLengthOfLCIS(self, nums: List[int]) -> int: rev = 0 ln = len(nums) if ln == 0 or ln == 1: return ln temp = 1 for i in range(1, ln): if nums[i]>nums[i-1]: temp += 1 else: rev = temp if temp > rev else rev temp = 1 rev = temp if temp > rev else rev return rev
參考
畫解算法:674. 最長連續遞增序列 – 最長連續遞增序列 – 力扣(LeetCode) (leetcode-cn.com)
以上就是go語言題解LeetCode674最長連續遞增序列的詳細內容,更多關於go題解最長連續遞增序列的資料請關註WalkonNet其它相關文章!
推薦閱讀:
- go語言題解LeetCode88合並兩個有序數組示例
- C++實現LeetCode(179.最大組合數)
- C++實現LeetCode(228.總結區間)
- C++實現LeetCode(152.求最大子數組乘積)
- C++實現LeetCode(209.最短子數組之和)