如何高效判断数组是否为严格递减序列的顺时针旋转形式

本文介绍一种时间复杂度 O(n)、空间复杂度 O(1) 的算法，用于准确判断一个整数数组是否由严格递减序列经一次顺时针旋转得到，并给出可直接运行的 Ja va 实现与关键边界分析。

判断一个数组是不是某个严格递减序列经过一次顺时针旋转后的结果——比如 [6,5,4,3,2,1] 旋转两次变成 [2,1,6,5,4,3]——这个问题乍一看有点绕，但抓住它的结构本质后，解法其实相当简洁。

先理清基本定义：原始递减序列满足 a[0] > a[1] > ... > a[n-1]；顺时针旋转 k 位后，数组呈现“两段递减 + 衔接合法”的形态。前半段（可能为空）和后半段各自严格递减，而且末尾元素必须大于等于首段的最大值——也就是原序列的最大值，即未旋转时的首个元素。

这里有一个非常关键的洞察：整个数组最多只允许出现一次“上升拐点”——也就是唯一一处 arr[i] > arr[i-1] 的位置。这个拐点就是旋转分割点：拐点左侧是原递减序列的尾部，右侧是头部。而原序列的最大值一定是 arr[0]（如果根本没有拐点，说明数组本身就是严格递减的，相当于旋转了 0 次，这种情况也应该返回 true）。

不过，光检测一次拐点还不够。举个例子：[43, 44, 11, 10, 9] 中 44 > 43 构成了一个拐点，看起来满足“单拐点”的条件，但 arr[n-1] = 9 小于 arr[0] = 43，这意味着它没法通过旋转还原成一个递减序列——旋转后末尾元素必须大于等于原首元素，才能形成闭环衔接。所以最终的验证条件需要三条：

• 至多有一个 i ∈ [1, n-1] 满足 arr[i] > arr[i-1]；
• 如果存在拐点，那么必须满足 arr[n-1] >= arr[0]；
• 如果没有拐点，数组本身严格递减，直接成立。

下面是优化后的 Ja va 实现，一次遍历搞定，没有额外数组开销，边界处理也很干净：

public static boolean isSortedAndRotated(int[] arr) {
    int n = arr.length;
    if (n <= 1) return true;
    int inflectionCount = 0;
    int firstElement = arr[0];
    // 遍历检查相邻关系，统计上升拐点
    for (int i = 1; i < n; i++) {
        if (arr[i] > arr[i - 1]) {
            inflectionCount++;
            if (inflectionCount > 1) {
                return false; // 多于一个拐点 → 不合法
            }
        }
    }
    // 无拐点：原数组已严格递减
    if (inflectionCount == 0) {
        return true;
    }
    // 有且仅有一个拐点：验证末尾能否衔接首段（即 arr[n-1] >= arr[0]）
    return arr[n - 1] >= firstElement;
}

验证几个示例：

• [10, 9, 44, 43, 11] → 拐点在 44 > 9（i=2），arr[4]=11 >= arr[0]=10 → true
• [43, 44, 11, 10, 9] → 拐点在 44 > 43（i=1），但 arr[4]=9 < arr[0]=43 → false
• [6, 5, 4, 3, 2, 1] → 无拐点 → true
• [2, 1, 6, 5, 4, 3] → 拐点在 6 > 1（i=2），arr[5]=3 >= arr[0]=2 → true

需要留意的地方：

• 这个解法要求“严格递减”，不支持重复元素（比如 [5,5,4,3,2] 会因为 5==5 不触发拐点，但违反严格性）；如果需求是非增序列（≥ 关系），需要把比较逻辑调整为 arr[i] >= arr[i-1] 并额外校验单调性。
• 输入为空或单元素数组，默认视为有效。
• 时间复杂度 O(n)，只遍历一次；空间复杂度 O(1)，没有额外数组开销。

这个方案简洁、健壮，彻底避免了分段边界处理错误和索引越界的风险，是解决这类旋转排序判定问题的推荐思路。