674.最长连续递增序列

linwt · linwt · commit 11be1ba2c1a7 · 2022-03-21T22:14:04.000+08:00
diff --git a/leetcode_Java/DoneTitle.txt b/leetcode_Java/DoneTitle.txt
@@ -77,6 +77,7 @@
 560. 和为 K 的子数组
 589. N叉树的前序遍历
 617. 合并二叉树
+674. 最长连续递增序列
 695. 岛屿的最大面积
 698. 划分为k个相等的子集
 714. 买卖股票的最佳时机含手续费
diff --git a/leetcode_Java/Solution0300.java b/leetcode_Java/Solution0300.java
@@ -2,9 +2,10 @@
 
 
 /*
+题目简化：求数组的最长递增子序列的长度
 1、定义dp数组：dp[i] 表示以索引i的元素结尾的最长递增子序列的长度
 2、状态转移方程：if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
-  位置i的最长递增子序列长度 等于j从0到i-1各个位置的 最长递增子序列加1的 最大值
+  位置i的最长递增子序列长度 等于j从0到i-1各个位置的 最长递增子序列长度加1的 最大值
 3、初始化：dp[i] = 1 表示每一个位置i的递增子序列的长度至少是1
 4、遍历dp数组填表：第一个for循环遍历dp数组的未知位置，第二个for循环遍历dp数组的已知位置，根据状态转移方程获取已知结果计算未知结果
 5、返回结果：遍历时比较每个位置结尾时的最长递增子序列的长度，并记录最大值，最后返回最大值
diff --git a/leetcode_Java/Solution0674.java b/leetcode_Java/Solution0674.java
@@ -0,0 +1,66 @@
+// 674. 最长连续递增序列
+
+
+/*
+动态规划：
+题目简化：求数组的最长连续递增子序列的长度
+1、定义dp数组：dp[i] 表示以索引i的元素结尾的最长连续递增子序列的长度
+2、初始化：dp[i] = 1 表示每一个位置i的连续递增子序列的长度至少是1
+3、状态转移方程：if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;
+  位置i的最长连续递增子序列长度 等于前一位置的最长连续递增子序列长度加1
+4、遍历dp数组填表：一个for循环遍历dp数组的未知位置，根据状态转移方程获取已知结果计算未知结果
+5、返回结果：遍历时比较每个位置结尾时的最长连续递增子序列的长度，并记录最大值，最后返回最大值
+ */
+class Solution {
+    public int findLengthOfLCIS(int[] nums) {
+        int n = nums.length;
+        int[] dp = new int[n];
+        Arrays.fill(dp, 1);
+        int res = 1;
+        for (int i = 1; i < n; i++) {
+            if (nums[i] > nums[i - 1]) {
+                dp[i] = dp[i - 1] + 1;
+                res = Math.max(res, dp[i]);
+            }
+        }
+        return res;
+    }
+}
+
+
+/*
+贪心：双指针，遍历数组，记录起始位置，当前元素比前一元素大时 计算连续递增子序列的长度 并保存最大值，否则将当前位置重新作为起始位置，最终返回最长连续递增子序列的长度
+ */
+class Solution {
+    public int findLengthOfLCIS(int[] nums) {
+        int start = 0;
+        int res = 1;
+        for (int i = 1; i < nums.length; i++) {
+            if (nums[i] > nums[i - 1]) {
+                res = Math.max(res, i - start + 1);
+            } else {
+                start = i;
+            }
+        }
+        return res;
+    }
+}
+
+
+/*
+贪心：变量计数
+ */
+class Solution {
+    public int findLengthOfLCIS(int[] nums) {
+        int count = 1;
+        int res = 1;
+        for (int i = 1; i < nums.length; i++) {
+            if (nums[i] > nums[i - 1]) {
+                res = Math.max(res, ++count);
+            } else {
+                count = 1;
+            }
+        }
+        return res;
+    }
+}
