Easy
题目描述
给定一个长度为 n 的整数数组 nums。
如果存在下标 0 < p < q < n - 1，使得：
- 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 和 q，将数组分成三段，每段都满足特定的单调性要求。
解题思路
根据题目要求，我们需要找到两个下标 p 和 q (0 < p < q < n-1)，使得：
- 第一段 [0, p] 严格递增
- 第二段 [p, q] 严格递减
- 第三段 [q, n-1] 严格递增
暴力枚举法（推荐）：
- 枚举所有可能的 p 和 q 值
- 对于每一对 (p, q)，检查三段是否都满足单调性要求
- 由于数组长度最大为 100，O(n³) 的时间复杂度完全可以接受
具体实现步骤：
- 外层循环枚举 p，范围是 [1, n-3]
- 内层循环枚举 q，范围是 [p+1, n-2]
- 对于每一对 (p, q)，检查三段的单调性
- 如果找到满足条件的 (p, q)，直接返回 true
- 如果所有组合都不满足，返回 false
这种方法直观易懂，符合题目提示的暴力解法思路。
代码实现
class Solution {
public:
bool isTrionic(vector<int>& nums) {
int n = nums.size();
for (int p = 1; p <= n - 3; p++) {
for (int q = p + 1; q <= n - 2; q++) {
bool valid = true;
// 检查第一段 [0, p] 是否严格递增
for (int i = 0; i < p; i++) {
if (nums[i] >= nums[i + 1]) {
valid = false;
break;
}
}
if (!valid) continue;
// 检查第二段 [p, q] 是否严格递减
for (int i = p; i < q; i++) {
if (nums[i] <= nums[i + 1]) {
valid = false;
break;
}
}
if (!valid) continue;
// 检查第三段 [q, n-1] 是否严格递增
for (int i = q; i < n - 1; i++) {
if (nums[i] >= nums[i + 1]) {
valid = false;
break;
}
}
if (valid) return true;
}
}
return false;
}
};
class Solution:
def isTrionic(self, nums: List[int]) -> bool:
n = len(nums)
for p in range(1, n - 2):
for q in range(p + 1, n - 1):
valid = True
# 检查第一段 [0, p] 是否严格递增
for i in range(p):
if nums[i] >= nums[i + 1]:
valid = False
break
if not valid:
continue
# 检查第二段 [p, q] 是否严格递减
for i in range(p, q):
if nums[i] <= nums[i + 1]:
valid = False
break
if not valid:
continue
# 检查第三段 [q, n-1] 是否严格递增
for i in range(q, n - 1):
if nums[i] >= nums[i + 1]:
valid = False
break
if valid:
return True
return False
public class Solution {
public bool IsTrionic(int[] nums) {
int n = nums.Length;
for (int p = 1; p <= n - 3; p++) {
for (int q = p + 1; q <= n - 2; q++) {
bool valid = true;
// 检查第一段 [0, p] 是否严格递增
for (int i = 0; i < p; i++) {
if (nums[i] >= nums[i + 1]) {
valid = false;
break;
}
}
if (!valid) continue;
// 检查第二段 [p, q] 是否严格递减
for (int i = p; i < q; i++) {
if (nums[i] <= nums[i + 1]) {
valid = false;
break;
}
}
if (!valid) continue;
// 检查第三段 [q, n-1] 是否严格递增
for (int i = q; i < n - 1; i++) {
if (nums[i] >= nums[i + 1]) {
valid = false;
break;
}
}
if (valid) return true;
}
}
return false;
}
}
/**
* @param {number[]} nums
* @return {boolean}
*/
var isTrionic = function(nums) {
const n = nums.length;
for (let p = 1; p <= n - 3; p++) {
for (let q = p + 1; q <= n - 2; q++) {
let valid = true;
// 检查第一段 [0, p] 是否严格递增
for (let i = 0; i < p; i++) {
if (nums[i] >= nums[i + 1]) {
valid = false;
break;
}
}
if (!valid) continue;
// 检查第二段 [p, q] 是否严格递减
for (let i = p; i < q; i++) {
if (nums[i] <= nums[i + 1]) {
valid = false;
break;
}
}
if (!valid) continue;
// 检查第三段 [q, n-1] 是否严格递增
for (let i = q; i < n - 1; i++) {
if (nums[i] >= nums[i + 1]) {
valid = false;
break;
}
}
if (valid) return true;
}
}
return false;
};
复杂度分析
| 复杂度类型 | 复杂度分析 |
|---|---|
| 时间复杂度 | O(n³) - 两层循环枚举 p 和 q，内部最多遍历 n 个元素检查单调性 |
| 空间复杂度 | O(1) - 只使用常数额外空间 |