给定无序数组arr, 返回其中最长的连续序列的长度(要求值连续, 位置可以不连续,例如 3,4,5,6为连续的自然数)- 先排序 (
O(NlngN)); - 然后使用滑动窗口模板;
- 易错点: 考虑
[0,1,1,2,3], 答案应该是 4 而不是 3;- 所以还要使用一个变量来记录区间内的重复值;
Python
class Solution:
def MLS(self , arr: List[int]) -> int:
N = len(arr)
arr.sort()
def check(l, r, rep): # O(1) 判断是否连续
return l < r and arr[r] - arr[l] != r - l - rep
l, r = 0, 0 # 闭区间窗口
rep = 0 # 记录区间内的重复次数
ret = 0
while r < N:
while check(l, r, rep): # 当不满足时, 右移 l
if l + 1 < N and arr[l] == arr[l + 1]:
rep -= 1
l += 1
ret = max(ret, r - l + 1 - rep)
if r + 1 < N and arr[r] == arr[r + 1]:
rep += 1
r += 1
return ret不算是标准的动态规划, 因为它不满足无后效性;
- 哈希表中的 key 和 value 分别表示什么?
- 区间长度
value和它的两个端点[key1, key2]; - 如果
value = 1, 则key1 == key2;
- 区间长度
- 算法流程:
- 初始化哈希表
book; - 遍历
arr中每个x; - 若
x不在book中, 执行:- 初始化
book[x] = 1表示区间[x, x]的长度为 1 (也可以理解为 x 出现过的标记); - 查询
l = book[x-1]和r = book[x+1], 分别表示x左右区间的长度, 若不存在则为0; 则[x-l, x+r]这段区间内的长度为l + 1 + r; - 根据
book的定义, 因为x把左右区间连通了, 所以需要更新book[x-l]和book[x+r]
- 初始化
- 初始化哈希表
- 为什么
book[x-1]和book[x+1]代表的区间一定在x两侧? 换言之, 为什么这两个区间是[x-l, x-1]和[x+1, x+r], 而不是[x-1, x+l]和[x-r, x+1]? ;- 因为执行上述操作的前提是
x没有出现过; 如果x出现过, 就和book的定义发生了冲突, 即违反了book[x - l] = book[x + r] = l + 1 + r这一步操作;
- 因为执行上述操作的前提是
Python
class Solution:
def MLS(self , arr: List[int]) -> int:
book = dict()
ret = 0
for x in arr:
if x not in book:
book[x] = 1
l, r = book.get(x - 1, 0), book.get(x + 1, 0)
mx = book[x - l] = book[x + r] = l + 1 + r
ret = max(ret, mx)
return ret