题解 | #牧场里的编号顺序#
牧场里的编号顺序
https://www.nowcoder.com/practice/6741b77f486a493da5258738323ddd3e?tpId=354&tqId=10589475&ru=/exam/oj&qru=/ta/interview-202-top/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D354
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param ids int整型一维数组 * @param n int整型 * @return int整型 */ public int longestConsecutive (int[] ids, int n) { // write code here int maxLength = 0; // 最长递增子序列的长度 int currentLength = 1; // 当前递增子序列的长度 for (int i = 1; i < n; i++) { if (ids[i] > ids[i - 1]) { currentLength++; // 如果当前数字大于前一个数字,递增子序列长度加一 } else { maxLength = Math.max(maxLength, currentLength); // 更新最长递增子序列长度 currentLength = 1; // 重置当前递增子序列长度 } } return Math.max(maxLength, currentLength); // 返回最长递增子序列长度 } }
知识点:
- 数组遍历:通过循环遍历数组元素,逐个检查递增关系。
- 条件判断:判断当前数字是否大于前一个数字,从而确定递增子序列是否连续。
- 最大值更新:使用 Math.max 函数来更新最长递增子序列的长度。
- 基本的时间复杂度分析:算法的时间复杂度是 O(n),因为我们只需要对数组进行一次遍历。
解题思路:
遍历输入数组,对于每个数字,我们检查它是否大于前一个数字。如果是,说明递增子序列连续,我们将当前长度加一。如果不是,说明递增子序列中断,我们将当前长度与最长长度比较,并重置当前长度为1。最后,我们返回最长长度。