3637. 三段式數組 I

思路

題目要求先嚴格遞增，再嚴格遞減，最後再嚴格遞增。
我們能用變數紀錄當前是遞增還是遞減，並在後續用xor判斷現在遞增遞減的狀態與之前是否相同，
假如不同，就代表狀態有所變化，原先的題目要求就轉化成「要求矩陣有兩次狀態變化」。

程式碼

class Solution {
public:
    bool isTrionic(vector<int>& nums) {
        if(nums.size() < 4) return false;
        int n = nums.size();
        int cnt = 0;
        bool dir = nums[1] > nums[0]; // 一開始是否遞增
        if(!dir) return false;
        for(int i = 1; i < n; i++) {
            if(nums[i] == nums[i - 1]) return false; // 數值相同，不嚴格
            if((nums[i] > nums[i - 1]) ^ dir) { // 方向是否變動
                dir = !dir;
                if(++cnt > 2) return false; // 變動次數增加，最大上限為 2
            }
        }
        return cnt == 2; // 恰好變動兩次
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$