如何判断Java List元素为升序排列且相邻元素固定差值为1

首先明确效率前提：这个校验逻辑的理论最优时间复杂度就是O(n)——你必须确认每一对相邻元素的差值为1，不存在复杂度更低的算法，你写的朴素遍历已经摸到了效率天花板，不同实现的差异只在鲁棒性、适配场景、代码风格、平均耗时上。

不同场景的实现参考 #

• 如果你只针对ArrayList使用，且追求最高的执行效率，可以在朴素遍历的基础上增加前置快速失败逻辑，减少无效遍历：

public static boolean checkSequenceList(List<Integer> li){
    int size = li.size();
    // 空列表、单元素列表天然符合要求
    if (size <= 1) {
        return true;
    }
    // O(1)时间做前置校验，首尾差不符合直接返回，不用遍历
    int first = li.get(0);
    int last = li.get(size - 1);
    if (last - first != size - 1) {
        return false;
    }
    // 首尾校验通过再遍历检查相邻元素
    for (int i = 0; i < size - 1; i++) {
        // 如果你的业务允许列表存null，记得在这里加非空判断避免空指针
        if (li.get(i+1) - li.get(i) != 1) {
            return false;
        }
    }
    return true;
}

这个实现没有改变最坏场景的O(n)复杂度，但如果业务中大部分不符合要求的列表首尾差就不对，平均执行效率会比纯遍历高很多。

• 如果你用Java 8及以上版本，偏好函数式的简洁写法，可以用Stream实现，逻辑更短，执行效率和普通遍历接近：

public static boolean checkSequenceList(List<Integer> li){
    if (li.size() <= 1) {
        return true;
    }
    return IntStream.range(0, li.size() - 1)
            .allMatch(i -> li.get(i+1) - li.get(i) == 1);
}

• 如果你的方法需要兼容LinkedList等不支持高效随机访问的List实现，不要用下标遍历，改用迭代器，避免时间复杂度退化成O(n²)：

public static boolean checkSequenceList(List<Integer> li){
    if (li.size() <= 1) {
        return true;
    }
    Iterator<Integer> it = li.iterator();
    Integer prev = it.next();
    while (it.hasNext()) {
        Integer curr = it.next();
        if (curr - prev != 1) {
            return false;
        }
        prev = curr;
    }
    return true;
}

注意：所有实现默认列表中不存null值，如果你的业务场景允许null元素，需要在做差值计算前补非空判断，否则会触发空指针异常。

内容的提问来源于stack exchange，提问作者StevenU