题目描述
给你一个整数数组 nums
。
返回数组 nums
中 严格递增 或 严格递减 的最长非空子数组的长度。
样例
输入:nums = [1,4,3,3,2]
输出:2
解释:
nums 中严格递增的子数组有[1]、[2]、[3]、[3]、[4] 以及 [1,4]。
nums 中严格递减的子数组有[1]、[2]、[3]、[3]、[4]、[3,2] 以及 [4,3]。
因此,返回 2。
输入:nums = [3,3,3,3]
输出:1
解释:
nums 中严格递增的子数组有 [3]、[3]、[3] 以及 [3]。
nums 中严格递减的子数组有 [3]、[3]、[3] 以及 [3]。
因此,返回 1。
输入:nums = [3,2,1]
输出:3
解释:
nums 中严格递增的子数组有 [3]、[2] 以及 [1]。
nums 中严格递减的子数组有 [3]、[2]、[1]、[3,2]、[2,1] 以及 [3,2,1]。
因此,返回 3。
限制
1 <= nums.length <= 50
1 <= nums[i] <= 50
算法
(线性遍历) $O(n)$
- 以求最长严格递增子数组为例,遍历数组并维护一个当前最长子数组的起始位置,如果当前位置不满足严格递增,则更新起始位置。每次遍历结束后,更新答案。
时间复杂度
- 遍历数组两次,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
private:
int comp(int x, int y) {
return x < y ? -1 : (x == y ? 0 : 1);
}
int solve(const vector<int> &nums, int d) {
const int n = nums.size();
int res = 1;
for (int i = 1, j = 0; i < n; i++) {
if (comp(nums[i - 1], nums[i]) != d)
j = i;
res = max(res, i - j + 1);
}
return res;
}
public:
int longestMonotonicSubarray(vector<int>& nums) {
return max(solve(nums, 1), solve(nums, -1));
}
};