数据结构与算法之动态规划: LeetCode 3105. 最长的严格递增或递减子数组 (Ts版)
最长的严格递增或递减子数组
- https://leetcode.cn/problems/longest-strictly-increasing-or-strictly-decreasing-subarray/description/
描述
- 给你一个整数数组 nums
- 返回数组 nums 中 严格递增 或 严格递减的最长非空子数组的长度
示例 1
输入：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
示例 2
输入：nums = [3,3,3,3]
输出：1
- 解释：
- nums 中严格递增的子数组有 [3]、[3]、[3] 以及 [3]
- nums 中严格递减的子数组有 [3]、[3]、[3] 以及 [3]
- 因此，返回 1
示例 3
输入：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
Typescript 版算法实现
1 ) 方案1: 分组循环
function longestMonotonicSubarray(a: number[]): number {let ans = 1;let i = 0, n = a.length;while (i < n - 1) {if (a[i + 1] === a[i]) {i++; // 直接跳过continue;}const i0 = i; // 记录这一组的开始位置const inc = a[i + 1] > a[i]; // 定下基调：是严格递增还是严格递减i += 2; // i 和 i+1 已经满足要求，从 i+2 开始判断while (i < n && a[i] !== a[i - 1] && (a[i] > a[i - 1]) === inc) {i++;}// 从 i0 到 i-1 是满足题目要求的（并且无法再延长的）子数组ans = Math.max(ans, i - i0);i--; // 回退一步以确保循环可以正确处理下一个元素}return ans;
}
2 ) 方案2: 分组循环优化版
function longestMonotonicSubarray(nums: number[]): number {const n = nums.length * 2;let i = 0, ans = 0;const doubledNums = [...nums, ...nums.reverse()]; // 拼接原数组和其反转while (i < n) {const st = i;i += 1;// 查找连续递增序列while (i < n && doubledNums[i] > doubledNums[i - 1]) {i += 1;}ans = Math.max(ans, i - st);}return ans;
}
3 ) 方案3: 动态规划
function longestMonotonicSubarray(nums: number[]): number {let dp0 = 1, dp1 = 1, len = 1, n = nums.length;// dp0 表示以当前元素为结尾的递增子数组的长度，dp1 表示以当前元素为结尾的递减子数组的长度for (let i = 1; i < n; i++) {dp0 = nums[i] > nums[i - 1] ? dp0 + 1 : 1;dp1 = nums[i] < nums[i - 1] ? dp1 + 1 : 1;len = Math.max(len, Math.max(dp0, dp1));}return len;
}