3350. 检测相邻递增子数组 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 * 10^5
  • -10^9 <= nums[i] <= 10^9

前后缀分解，然后遍历

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(List<Integer> l) {
        int nums[] = l.stream().mapToInt(i -> i).toArray();
        int n = nums.length, res = 0;
        // pre[1:n]: 之前位置到当前位置的最长递增区间长度
        // suf[0:n-1]: 当前位置到后面位置的最长递增区间长度
        int pre[] = new int[n+1], suf[] = new int[n+1];
        for (int i = 0; i < n; i++) {
            if (i == 0 || nums[i] > nums[i-1]) pre[i+1] = pre[i] + 1;
            else pre[i+1] = 1;
        }
        for (int i = n-1; i >= 0; i--) {
            if (i == n-1 || nums[i] < nums[i+1]) suf[i] = suf[i+1] + 1;
            else suf[i] = 1;
        }
        // 枚举第二个子数组的起始位置
        for (int i = 1; i < n; i++) {
            res = Math.max(res, Math.min(pre[i], suf[i]));
        }
        return res;
    }
}

灵神：记录当前和上一个最长递增区间长度做法

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(List<Integer> nums) {
        int arr[] = nums.stream().mapToInt(i -> i).toArray();
        int n = arr.length;
        int cnt = 1, preCnt = 0, res = 0;
        // 枚举数组每个位置，计算当前的最长递增区间长度，并记录之前的最长递增区间长度
        // 对于当前位置，有两种情况
        // 两个子数组都在当前递增区间
        // 第一个子数组在上一个递增区间，第二子数组在当前递增区间
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i-1]) {
                cnt++;
            }
            else {
                preCnt = cnt;
                cnt = 1;
            }
            res = Math.max(res, Math.max(cnt/2, Math.min(cnt, preCnt)));
        }
        return res;
    }
}

周赛做的，二分+TreeSet，勉强过（丑陋

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public boolean hasIncreasingSubarrays(TreeSet<Integer> set, int n, int k) {
        // int n = nums.size();
        for (int i = 0; i < n; i++) {
            int nxt = i+k;
            if (nxt >= n) break;
            int c1 = (int)set.higher(i), c2 = (int)set.higher(nxt);
            if (c1 - i >= k && c2 - nxt >= k) return true;
        }
        return false;
    }
    public int maxIncreasingSubarrays(List<Integer> nums) {
        int n = nums.size();
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 1; i < n; i++) {
            if (nums.get(i) <= nums.get(i-1)) {
                set.add(i);
                // 5, 8, 9
            }
        }
        set.add(n);
        int l = 0, r = n/2+1;
        while (l < r) {
            int mid = l + (r-l)/2;
            if (hasIncreasingSubarrays(set, n, mid)) l = mid+1;
            else r = mid;
        }
        return l-1;
    }
}