LeetCode 题解工作台
三段式数组 I
给你一个长度为 n 的整数数组 nums 。 如果存在索引 0 ，使得数组满足以下条件，则称其为 三段式数组（trionic） ： nums[0...p] 严格 递增， nums[p...q] 严格 递减， nums[q...n − 1] 严格 递增。 如果 nums 是三段式数组，返回 true …
0
题型
6
代码语言
0
相关题
当前训练重点
简单 · trionic·数组·i·core·interview·pattern
答案摘要
我们首先定义一个指针 ，初始时 $p = 0$，表示当前指向数组的第一个元素。我们将 向右移动，直到找到第一个不满足严格递增的元素，即 $nums[p] \geq nums[p + 1]$。如果此时 $p = 0$，说明数组的前半部分没有严格递增的部分，因此直接返回 。 接下来，我们定义另一个指针 ，初始时 $q = p$，表示当前指向数组的第二个部分的第一个元素。我们将 向右移动，直到找到第…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 trionic·数组·i·core·interview·pattern 题型思路
题目描述
给你一个长度为 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
解题思路
方法一：一次遍历
我们首先定义一个指针 ，初始时 ，表示当前指向数组的第一个元素。我们将 向右移动，直到找到第一个不满足严格递增的元素，即 。如果此时 ，说明数组的前半部分没有严格递增的部分，因此直接返回 。
接下来，我们定义另一个指针 ，初始时 ，表示当前指向数组的第二个部分的第一个元素。我们将 向右移动，直到找到第一个不满足严格递减的元素，即 。如果此时 或者 ，说明数组的第二部分没有严格递减的部分或者没有第三部分，因此直接返回 。
如果以上条件都满足，说明数组是三段式的，返回 。
时间复杂度 ，其中 是数组的长度。空间复杂度 ，只使用了常数级别的额外空间。
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the method: brute force can reach O(n^2), prefix/suffix optimization can reduce it to O(n). Space complexity is O(n) if storing auxiliary arrays for prefix and suffix tracking. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Looking for correct detection of trionic index patterns in array splits.
- question_mark
Expect candidates to avoid unnecessary nested loops when possible.
- question_mark
Interest in whether early termination and index reasoning are applied.
常见陷阱
外企场景- error
Failing to respect the strict index constraints 0 < p < q < n-1.
- error
Checking all pairs without optimization, leading to timeouts for larger n.
- error
Misidentifying sequences when array values are equal or negative.
进阶变体
外企场景- arrow_right_alt
Trionic Array II with reversed conditions or modified comparison rules.
- arrow_right_alt
Arrays with additional constraints, such as strictly increasing or decreasing segments.
- arrow_right_alt
Counting the total number of trionic sequences instead of just existence.