【LetMeFly】3350.检测相邻递增子数组 II：将数组分成多段递增
力扣题目链接：https://leetcode.cn/problems/adjacent-increasing-subarrays-detection-ii/
给你一个由 n 个整数组成的数组 nums ，请你找出 k 的 最大值，使得存在 两个 相邻 且长度为 k 的 严格递增 子数组。具体来说，需要检查是否存在从下标 a 和 b (a < b) 开始的 两个 子数组，并满足下述全部条件：
- 这两个子数组
nums[a..a + k - 1] 和 nums[b..b + k - 1] 都是 严格递增 的。
- 这两个子数组必须是 相邻的，即
b = a + k。
返回 k 的 最大可能 值。
子数组 是数组中的一个连续 非空 的元素序列。
示例 1：
输入：nums = [2,5,7,8,9,2,3,4,3,1]
输出：3
解释：
- 从下标 2 开始的子数组是
[7, 8, 9]，它是严格递增的。
- 从下标 5 开始的子数组是
[2, 3, 4]，它也是严格递增的。
- 这两个子数组是相邻的，因此 3 是满足题目条件的 最大
k 值。
示例 2：
输入：nums = [1,2,3,4,4,4,4,5,6,7]
输出：2
解释：
- 从下标 0 开始的子数组是
[1, 2]，它是严格递增的。
- 从下标 2 开始的子数组是
[3, 4]，它也是严格递增的。
- 这两个子数组是相邻的，因此 2 是满足题目条件的 最大
k 值。
提示：
2 <= nums.length <= 2 * 105-109 <= nums[i] <= 109
解题方法：一次遍历
数组[2,5,7,8,9,2,3,4,3,1]由四个递增数组组成：[2,5,7,8,9]、[2,3,4]、[3]、[1]，他们的长度分别是4、3、1、1。
- 对于相邻的长度为4、3的递增数组，可以设置$k=min(4,3)=3$
- 对于单个长度为4的递增数组，可以设置$k=\lfloor\frac42\rfloor$
一遍遍历更新并计算上述两个值中最大的那个作为答案。
- 时间复杂度$O(len(nums))$
- 空间复杂度$O(1)$
AC代码
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
int maxIncreasingSubarrays(vector<int>& nums) {
int ans = 0;
for (int lastCnt = 0, nowCnt = 0, i = 0; i < nums.size(); i++) {
nowCnt++;
if (i == nums.size() - 1 || nums[i] >= nums[i + 1]) {
ans = max({ans, min(lastCnt, nowCnt), nowCnt / 2});
lastCnt = nowCnt, nowCnt = 0;
}
}
return ans;
}
};
|
C++ - 写法2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public:
int maxIncreasingSubarrays(vector<int>& nums) {
int ans = 1;
int lastVal = 1000000001, lastCnt = 0, nowCnt = 0;
for (int t : nums) {
if (t <= lastVal) {
ans = max(ans, min(lastCnt, nowCnt));
ans = max(ans, nowCnt / 2);
printf("ans = %d, t = %d, lastCnt = %d, nowCnt = %d\n", ans, t, lastCnt, nowCnt);
lastCnt = nowCnt, nowCnt = 1;
} else {
nowCnt++;
}
lastVal = t;
}
return max({ans, min(lastCnt, nowCnt), nowCnt / 2});
}
};
|
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| '''
LastEditTime: 2025-10-15 22:23:10
'''
from typing import List
class Solution:
def maxIncreasingSubarrays(self, nums: List[int]) -> int:
ans = lastCnt = nowCnt = 0
for i in range(len(nums)):
nowCnt += 1
if i == len(nums) - 1 or nums[i] >= nums[i + 1]:
ans = max(ans, min(lastCnt, nowCnt), nowCnt // 2)
lastCnt = nowCnt
nowCnt = 0
return ans
|
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public int maxIncreasingSubarrays(List<Integer> nums) {
int ans = 0;
for (int i = 0, lastCnt = 0, nowCnt = 0; i < nums.size(); i++) {
nowCnt++;
if (i == nums.size() - 1 || nums.get(i) >= nums.get(i + 1)) {
ans = Math.max(ans, Math.max(Math.min(lastCnt, nowCnt), nowCnt / 2));
lastCnt = nowCnt;
nowCnt = 0;
}
}
return ans;
}
}
|
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
package main
func maxIncreasingSubarrays(nums []int) int {
ans, lastCnt, nowCnt := 0, 0, 0
for i, t := range nums {
nowCnt++
if i == len(nums) - 1 || t >= nums[i + 1] {
ans = max(ans, max(min(lastCnt, nowCnt), nowCnt / 2))
lastCnt, nowCnt = nowCnt, 0
}
}
return ans
}
|
Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
impl Solution {
pub fn max_increasing_subarrays(nums: Vec<i32>) -> i32 {
let mut ans: i32 = 0;
let mut last_cnt: i32 = 0;
let mut now_cnt: i32 = 0;
for i in 0..nums.len() {
now_cnt += 1;
if i == nums.len() - 1 || nums[i] >= nums[i + 1] {
ans = ans.max(last_cnt.min(now_cnt)).max(now_cnt / 2);
last_cnt = now_cnt;
now_cnt = 0;
}
}
ans
}
}
|
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
千篇源码题解已开源