3350. 檢測相鄰遞增子數組 II

小貼士：if(a || b)，當條件a成立時，條件b不會被判斷，直接進入內容，所以下方的判斷式不會發生nums[i + 1]越界的問題。

if(i == nums.size() - 1 || nums[i] >= nums[i + 1]) {...}

前後綴判斷

思路

要判斷相鄰，長度為k，相鄰的兩個嚴格遞增子數組。 可以先計算對於每一個位置i的數字而言。

1. 以自己為終點，最長的嚴格遞增子數組。叫做 prefix[i]
2. 以自己為起點，最長的嚴格遞增子數組。叫做 suffix[i]

現在要找到最長的長度k，可以參考的答案有哪些？ 對於位置i而言，滿足題目條件的最大k是 max(prefix[i], suffix[i + 1])， 因此遍歷i，更新答案就行。 *計算前綴的迴圈能跟更新答案的迴圈合併，節省一半的空間。

程式碼

class Solution {
public:
    int maxIncreasingSubarrays(vector<int>& nums) {
        int n = nums.size();
        vector<int> prefix(n), suffix(n);
        prefix[0] = 1;
        for(int i = 1; i < n; ++i) {
            if(nums[i - 1] < nums[i]) {
                prefix[i] = prefix[i - 1] + 1;
            }
            else {
                prefix[i] = 1;
            }
        }
        suffix.back() = 1;
        for(int i = n - 2; i >= 0; --i) {
            if(nums[i] < nums[i + 1]) {
                suffix[i] = suffix[i + 1] + 1;
            }
            else {
                suffix[i] = 1;
            }
        }
        int res = 0;
        for(int i = 0; i < n - 1; ++i) {
            res = max(res, min(prefix[i], suffix[i + 1]));
        }
        return res;
    }
};

優化

兩個連續遞增子數組的兩種可能如下。

1. 將一個大的連續遞增子數組拆開來。
2. 前面一個遞增，後面一個遞增，兩者不可合併成一個更大的。

假如想只用一次遍歷就求得答案，首先紀錄遞增序列的長度，假如新的數字加入破壞了數字的連續遞增，
將pre_cnt作為前綴，重置cnt。
pre_cnt是前面的遞增子數組長度，cnt是現在的。

當遍歷到結尾，或是遞增被破壞，答案更新。
狀況一，最好的拆法是大小相同，因此為cnt/2
狀況二，前面遞增長度為pre_cnt，後面遞增長度cnt，答案為兩者取最小。

程式碼

class Solution {
public:
    int maxIncreasingSubarrays(vector<int>& nums) {
        int n = nums.size();
        int res = 0, pre_cnt = 0, cnt = 0;
        for(int i = 0; i < n; ++i) {
            ++cnt;
            if(i == n - 1 || nums[i] >= nums[i + 1]) {
                res = max({res, cnt / 2, min(pre_cnt, cnt)});
                pre_cnt = cnt;
                cnt = 0;
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：方法一 $O(n)$，方法二 $O(1)$