leetcode每日一题 P3350 检测相邻递增子数组 II

---

时间轴

时间轴

2025-10-15

init

数组，从O(n3)优化到O(n2)再优化到O(n)

---

题目：

P3350 检测相邻递增子数组 II

https://leetcode.cn/problems/adjacent-increasing-subarrays-detection-ii/description/?envType=daily-question&envId=2025-10-15

$$ O(n^3)$$ 穷举

直接穷举，没啥好说的，超时

#include <vector>
using std::vector;

class Solution {
public:
  int maxIncreasingSubarrays(vector<int> &nums) {
    int n = nums.size();
    // n从2开始
    int k = n / 2;
    int a, b, i;
    int flag = true;

    while (k > 0) {
      a = 0;     // 0..k-1
      b = a + k; // a+k.. b+k-1
      while (b + k - 1 < n) {
        flag = true;
        for (i = 1; i < k; i++) {
          if (nums[a + i] > nums[a + i - 1] && nums[b + i] > nums[b + i - 1]) {
            continue;
          } else {
            a++;
            b = a + k;
            flag = false;
            break;
          }
        }
        if (flag) {
          return k;
        }
      }
      k--;
    }
    return 0;
  }
};

#include <stdio.h>
int main() {
  vector<int> vec = {19, -14, 0, 9};
  Solution s;
  printf("%d\n", s.maxIncreasingSubarrays(vec));
}

$$O(n^2)$$ 预处理优化

我们定义一个数组 inc, inc[i]表示以 nums[i] 结尾的最长递增子数组的长度。a，b 开始的两个数据段相邻且递增必定满足 inc[a + k - 1] >= k && inc[b + k - 1] >= k。这个也超时了呜呜。

#include <vector>
using std::vector;

class Solution {
public:
  int maxIncreasingSubarrays(vector<int> &nums) {
    int n = nums.size();
    int i;
    // n从2开始
    int k = n / 2;
    int a, b;
    vector<int> inc(n, 1);
    for (i = 1; i < n; i++) {
      if (nums[i] > nums[i - 1]) {
        inc[i] = inc[i - 1] + 1;
      }
    }

    while (k > 0) {
      a = 0;
      b = a + k;
      while (b + k - 1 < n) {
        if (inc[a + k - 1] >= k && inc[b + k - 1] >= k) {
          return k;
        } else {
          a++;
          b = a + k;
        }
      }
      k--;
      if (k == 1) {
        return 1;
      }
    }
    return 1;
  }
};

$$O(n)$$

如果我们知道所有严格递增的两个相邻数据段，那么 k 为这两个段的最小值。我们遍历一遍数组，找到 k 的最大值即可。但要注意，我们还需要记录单个严格递增段的长度，因为它也可以拆成两个严格递增的两个相邻数据段。

// #include <limits.h>
#include <vector>
using std::vector;

class Solution {
public:
  // 遍历数组，计算所有连续递增段的长度。
  int maxIncreasingSubarrays(vector<int> &nums) {
    int n = nums.size();
    int i;

    int curr_len = 1;
    // prev_len取0，否则第一次判断时会更新max，即使前面没有数据段
    int prev_len = 0;
    int max_val = 0;

    int len_max = 0;
    if (n <= 1) {
      return 0;
    }

    for (i = 1; i < n; i++) {
      if (nums[i] > nums[i - 1]) {
        curr_len++;
      } else {
        max_val = std::max(max_val, std::min(curr_len, prev_len));
        len_max = std::max(curr_len, len_max);
        prev_len = curr_len;
        curr_len = 1;
      }
    }
    // 最后不要忘了更新len_max
    len_max = std::max(len_max, curr_len);

    max_val = std::max(max_val, std::min(curr_len, prev_len));
    max_val = std::max(len_max / 2, max_val);

    return max_val;
  }
};