3637. 三段式数组 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

解法

方法一：一次遍历

我们首先定义一个指针 \(p\)，初始时 \(p = 0\)，表示当前指向数组的第一个元素。我们将 \(p\) 向右移动，直到找到第一个不满足严格递增的元素，即 \(nums[p] \geq nums[p + 1]\)。如果此时 \(p = 0\)，说明数组的前半部分没有严格递增的部分，因此直接返回 \(\text{false}\)。

接下来，我们定义另一个指针 \(q\)，初始时 \(q = p\)，表示当前指向数组的第二个部分的第一个元素。我们将 \(q\) 向右移动，直到找到第一个不满足严格递减的元素，即 \(nums[q] \leq nums[q + 1]\)。如果此时 \(q = p\) 或者 \(q = n - 1\)，说明数组的第二部分没有严格递减的部分或者没有第三部分，因此直接返回 \(\text{false}\)。

如果以上条件都满足，说明数组是三段式的，返回 \(\text{true}\)。

时间复杂度 \(O(n)\)，其中 \(n\) 是数组的长度。空间复杂度 \(O(1)\)，只使用了常数级别的额外空间。

Python3JavaC++GoTypeScript

class Solution:
    def isTrionic(self, nums: List[int]) -> bool:
        n = len(nums)
        p = 0
        while p < n - 2 and nums[p] < nums[p + 1]:
            p += 1
        if p == 0:
            return False
        q = p
        while q < n - 1 and nums[q] > nums[q + 1]:
            q += 1
        if q == p or q == n - 1:
            return False
        while q < n - 1 and nums[q] < nums[q + 1]:
            q += 1
        return q == n - 1

class Solution {
    public boolean isTrionic(int[] nums) {
        int n = nums.length;
        int p = 0;
        while (p < n - 2 && nums[p] < nums[p + 1]) {
            p++;
        }
        if (p == 0) {
            return false;
        }
        int q = p;
        while (q < n - 1 && nums[q] > nums[q + 1]) {
            q++;
        }
        if (q == p || q == n - 1) {
            return false;
        }
        while (q < n - 1 && nums[q] < nums[q + 1]) {
            q++;
        }
        return q == n - 1;
    }
}

class Solution {
public:
    bool isTrionic(vector<int>& nums) {
        int n = nums.size();
        int p = 0;
        while (p < n - 2 && nums[p] < nums[p + 1]) {
            p++;
        }
        if (p == 0) {
            return false;
        }
        int q = p;
        while (q < n - 1 && nums[q] > nums[q + 1]) {
            q++;
        }
        if (q == p || q == n - 1) {
            return false;
        }
        while (q < n - 1 && nums[q] < nums[q + 1]) {
            q++;
        }
        return q == n - 1;
    }
};

func isTrionic(nums []int) bool {
    n := len(nums)
    p := 0
    for p < n-2 && nums[p] < nums[p+1] {
        p++
    }
    if p == 0 {
        return false
    }
    q := p
    for q < n-1 && nums[q] > nums[q+1] {
        q++
    }
    if q == p || q == n-1 {
        return false
    }
    for q < n-1 && nums[q] < nums[q+1] {
        q++
    }
    return q == n-1
}

function isTrionic(nums: number[]): boolean {
    const n = nums.length;
    let p = 0;
    while (p < n - 2 && nums[p] < nums[p + 1]) {
        p++;
    }
    if (p === 0) {
        return false;
    }
    let q = p;
    while (q < n - 1 && nums[q] > nums[q + 1]) {
        q++;
    }
    if (q === p || q === n - 1) {
        return false;
    }
    while (q < n - 1 && nums[q] < nums[q + 1]) {
        q++;
    }
    return q === n - 1;
}

3637. 三段式数组 I

题目描述

解法

方法一：一次遍历

评论