- Leetcode 3350. Adjacent Increasing Subarrays Detection II
- 1. 解题思路
- 2. 代码实现
- 题目链接:3350. Adjacent Increasing Subarrays Detection II
1. 解题思路
这一题要获得最大的相邻递增子序列,显然就是从以下两种情况当中获取最大值:
- 从某一段连续的递增子序列拆成两个等长的子序列
- 从两个相邻的递增子序列当中截取等长的两个子序列
对前者,其最大长度就是其原本序列长度的一半,对后者,其最大长度就是两个连续递增子序列的长度较小值。
因此,我们我们只需要先找出原始数组当中全部的递增子序列,分别考察上述两种情况即可得到我们最终的答案。
2. 代码实现
给出python代码实现如下:
class Solution:def maxIncreasingSubarrays(self, nums: List[int]) -> int:s = []pre, cnt = -math.inf, 0for num in nums:if num <= pre:s.append(cnt)cnt = 0pre = numcnt += 1if cnt > 0:s.append(cnt)n = len(s)ans = max(x // 2 for x in s)for i in range(n-1):ans = max(ans, min(s[i], s[i+1]))return ans
提交代码评测得到:耗时1274ms,占用内存44.7MB。