给定一个整数数组 $b[n]$,$b$ 中连续的相等元素构成的子序列称为平台。试设计算法,求出 $b$ 中最长平台的长度。
时间: 2023-06-05 15:47:42 浏览: 142
求最长公共子序列
5星 · 资源好评率100%
题目描述:给定一个整数数组 $b[n]$,$b$ 中连续的相等元素构成的子序列称为平台。试设计算法,求出 $b$ 中最长平台的长度。
解答:设当前平台长度为 $len$,当前扫描的元素为 $b[i]$。若 $b[i] = b[i-1]$,则当前连续相等元素个数增加 $1$;否则,当前元素为新的平台起点,将当前平台长度 $len$ 和已知的最长平台长度 $maxLen$ 取较大值,然后将 $len$ 重置为 $1$。最后,将 $maxLen$ 返回。
具体实现如下:
```python
def longest_platform(b):
len, maxLen = 1, 1
for i in range(1, len(b)):
if b[i] == b[i-1]:
len += 1
else:
maxLen = max(maxLen, len)
len = 1
maxLen = max(maxLen, len)
return maxLen
```
时间复杂度:$O(n)$。
阅读全文