3637.三段式数组 I：一次遍历（三种实现）

【LetMeFly】3637.三段式数组 I：一次遍历（三种实现）

力扣题目链接：https://leetcode.cn/problems/trionic-array-i/

给你一个长度为 n 的整数数组 nums。

如果存在索引 0 < p < q < n − 1，使得数组满足以下条件，则称其为 三段式数组（trionic）：

• nums[0...p] 严格 递增，
• nums[p...q] 严格 递减，
• nums[q...n − 1] 严格 递增。

如果 nums 是三段式数组，返回 true；否则，返回 false。

 

示例 1:

输入: nums = [1,3,5,4,2,6]

输出: true

解释:

选择 p = 2, q = 4：

• nums[0...2] = [1, 3, 5] 严格递增 (1 < 3 < 5)。
• nums[2...4] = [5, 4, 2] 严格递减 (5 > 4 > 2)。
• nums[4...5] = [2, 6] 严格递增 (2 < 6)。

示例 2:

输入: nums = [2,1,3]

输出: false

解释:

无法选出能使数组满足三段式要求的 p 和 q 。

 

提示:

• 3 <= n <= 100
• -1000 <= nums[i] <= 1000

解题方法：遍历

使用一个状态$state$分别代表正在处于三个数组的那一段。

方法一：if-else

• 如果之前处于第1段数组且当前元素比上一个小，则跳转到第2段数组；
• 如果之前处于第2段数组且当前元素比上一个大，则跳转到第3段数组；
• 如果之前处于第3段数组且当前元素比上一个小，则返回false。

最终如果处于第三段数组则返回true。

方法二：累加$state$

只要发生数组跳跃，就一定是”当前元素比上个小且上个元素比上上个大” 或 “当前元素比上个大且上个元素比上上个小”，总之就是数组由增变减或由减变增，此时$state+1$。

最终如果处于第三段数组则返回true。

What’s more

1. 记得特判$nums[1]$和$nums[0]$的大小
2. 数组中不得出现相邻且相等的元素，记得特判

时空复杂度分析

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(1)$

AC代码

C++ - 方法一

/*
 * @LastEditTime: 2026-02-04 21:56:05
 */
class Solution {
public:
    bool isTrionic(vector<int>& nums) {
        int state = 0;
        if (nums[1] <= nums[0]) {
            return false;
        }
        for (int i = 2; i < nums.size(); i++) {
            if (nums[i] == nums[i - 1]) {
                return false;
            }
            if (state == 0) {
                if (nums[i] < nums[i - 1]) {
                    state = 1;
                }
            } else if (state == 1) {
                if (nums[i] > nums[i - 1]) {
                    state = 2;
                }
            } else if (state == 2) {
                if (nums[i] < nums[i - 1]) {
                    return false;
                }
            }
        }
        return state == 2;
    }
};

C++ - 方法一+if合并版

/*
 * @Author: LetMeFly
 * @Date: 2026-02-04 21:57:20
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2026-02-04 21:58:07
 */
#if defined(_WIN32) || defined(__APPLE__)
#include "_[1,2]toVector.h"
#endif

class Solution {
public:
    bool isTrionic(vector<int>& nums) {
        int state = 0;
        if (nums[1] <= nums[0]) {
            return false;
        }
        for (int i = 2; i < nums.size(); i++) {
            if (nums[i] == nums[i - 1]) {
                return false;
            }
            if (state == 0 && nums[i] < nums[i - 1]) {
                state = 1;
            } else if (state == 1 && nums[i] > nums[i - 1]) {
                state = 2;
            } else if (state == 2 && nums[i] < nums[i - 1]) {
                return false;
            }
        }
        return state == 2;
    }
};

C++ - 方法二

/*
 * @LastEditTime: 2026-02-04 22:02:00
 */
class Solution {
public:
    bool isTrionic(vector<int>& nums) {
        int state = 0;
        if (nums[1] <= nums[0]) {
            return false;
        }
        for (int i = 2; i < nums.size(); i++) {
            if (nums[i] == nums[i - 1]) {
                return false;
            }
            if ((nums[i] > nums[i - 1]) != (nums[i - 1] > nums[i - 2])) {
                state++;
                if (state > 2) {
                    return false;
                }
            }
        }
        return state == 2;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源