【LeetCode】674. Longest Continuous Increasing Subsequence 解题报告(Python)
2024-09-08 16:07:30
作者: 负雪明烛
id: fuxuemingzhu
个人博客: http://fuxuemingzhu.cn/
题目地址:https://leetcode.com/problems/longest-continuous-increasing-subsequence/description/
题目描述
Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray).
Example 1:
Input: [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3.
Even though [1,3,5,7] is also an increasing subsequence, it's not a continuous one where 5 and 7 are separated by 4.
Example 2:
Input: [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2], its length is 1.
Note: Length of the array will not exceed 10,000.
题目大意
找出数组中最长连续递增子序列(子数组)
解题方法
动态规划
直接使用dp作为到某个位置的最长连续子序列。所以,如果当前的值比前一个值大,那么dp应该是前面的一个位置的数值+1,否则当前的值应该是1。另外需要注意的是当输入是空的时候,应该返回0.
class Solution(object):
def findLengthOfLCIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums: return 0
N = len(nums)
dp = [1] * N
for i in range(1, N):
if nums[i] > nums[i - 1]:
dp[i] = dp[i - 1] + 1
return max(dp)
空间压缩DP
在上面的做法中看出,每步的结果之和上面一步有关,所以可以优化空间复杂度。
class Solution(object):
def findLengthOfLCIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
longest = 0
cur = 0
for i in range(len(nums)):
if i == 0 or nums[i] > nums[i - 1]:
cur += 1
longest = max(longest, cur)
else:
cur = 1
return longest
二刷的时候版本。
class Solution(object):
def findLengthOfLCIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums: return 0
N = len(nums)
dp = 1
res = 1
for i in range(1, N):
if nums[i] > nums[i - 1]:
dp += 1
res = max(res, dp)
else:
dp = 1
return res
日期
2018 年 1 月 29 日
2018 年 11 月 19 日 —— 周一又开始了
最新文章
- Swing布局管理器介绍
- NetworkError: 404 Not Found - http://www.companyName.com/Content/fonts/ubuntu-regular-webfont.woff2
- php中的正则函数主要有三个-正则匹配,正则替换
- csharp: 百度语音合成
- Java 集合系列 09 HashMap详细介绍(源码解析)和使用示例
- java gui三个组件的使用
- 201621123060《JAVA程序设计》第一周学习总结
- H5的学习之旅-H5的实体(14)
- MYSQL事务处理失效原因
- 【Android开发】之Fragment与Acitvity通信
- sql中的函数
- 解题(LevenshteinInstance--Levenshtein距离)
- Intellij Idea免费激活方法
- Centos 6.5下的OPENJDK卸载和SUN的JDK安装、环境变量配置
- UnityShader学习笔记1 — — 入门知识整理
- shiro学习笔记_0700_整合ssm
- IT行业所面临的问题
- ARM Linux 内核 panic 之cache 一致性 ——cci-400 cache一致互联
- idea调节字体大小
- 如何理解流Stream