当前位置：首页 > article >正文

Leetcode 3350 Adjacent Increasing Subarrays Detection II

article 2024/11/14 0:33:36

题意：有一个数组，求最大值k，满足两个相邻的长度为k的子数组是严格递增的。

题解：满足两个相邻的长度为k的子数组是严格递增的，这个验证起来是比较容易的，求解是比较难的。想到可能可以二分。
问题转化成，验证两个相邻的长度为k的子数组是严格递增的。
子数组严格递增的问题可以想到用dp

class Solution {
public:
    int maxIncreasingSubarrays(vector<int>& nums) {
        int l = 0;
        int r = nums.size() / 2;
        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if(hasIncreasingSubarrays(nums,mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
    

    bool hasIncreasingSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> dp(n, 1);
        for(int i = 1; i < n; i++) {
            if(nums[i] > nums[i-1]) {
                dp[i] = dp[i-1] + 1;
            }
        }  

        for(int i = 0; i <= n - k - 1; i++) {
            if(dp[i] >= k && dp[i+k] >= k)
                return true;
        }
        return false;
    }
};