最长连续递增序列

发表于
本文字数： 959 阅读时长 ≈ 1 分钟

LeetCode每日一题，674 Longest Continuous Increasing Subsequence

先看题目描述

sHrHr6.png

题目大意是给定一个数组 nums，让我们求出 nums 中最长连续递增子数组的长度并返回

算法和思路

贪心算法

这题比较简单，用贪心算法从前往后遍历就可以，要初始化几个变量，ans 维护当前的最长连续递增子数组长度，pre 维护上一个数字的值，cur 维护当前正在遍历的连续递增子数组长度

当遍历到数字 num 时：

  • 若 num > pre，说明当前的连续递增子数组长度可以继续增加，将 cur + 1，pre = num
  • 若 num <= pre，说明该连续递增子数组结束，将开始下一个连续递增子数组的判断，令 ans 取 ans 和 cur 之间的最大值，cur = 1，pre = num

遍历结束时，可能还有一个连续递增子数组未结束判断，该连续递增子数组的长度可能是最大的，因此也得考虑，令 ans 取 ans 和 cur 之间的最大值，最终返回 ans 即可

算法源码

贪心算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int ans = 0;
        int pre = Integer.MIN_VALUE;
        int cur = 0;
        for (int num : nums) {
            if (num > pre) {
                cur++;
                pre = num;
            } else {
                ans = Math.max(cur, ans);
                cur = 1;
                pre = num;
            }
        }
        ans = Math.max(ans, cur);
        return ans;
    }
}