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

本文介绍一种高效、鲁棒的方法，用于判断整数数组是否由某个严格递减序列经一次（或多次）顺时针旋转得到，重点解决边界误判问题（如 [43, 44, 11, 10, 9] 应返回 false）。

先说说核心思路。要判断一个数组是否由严格递减序列旋转而来，关键得抓住它的结构本质。一个严格递减序列（比如 6 > 5 > 4 > 3 > 2 > 1）经过顺时针旋转后，会形成**至多一个“上升拐点”**——也就是出现 arr[i] > arr[i-1] 的位置。这个拐点必须同时满足两个条件： 1. **唯一性**：整个数组里最多只能出现一次 arr[i] > arr[i-1]；如果出现两次或更多，那原始序列肯定不是严格递减的。 2. **环状一致性**：如果存在拐点（假设在索引 i 处），那么末尾元素 arr[n-1] 必须 **≥ 拐点左侧所有元素中的最大值**（也就是原递减序列的首元素），这样才能保证旋转后闭环成立。 举个例子： - ✅ [10, 9, 44, 43, 11] → 拐点在 9→44（索引 1→2），arr[4]=11 ≥ arr[0]=10 → 合法； - ❌ [43, 44, 11, 10, 9] → 拐点在 43→44（索引 0→1），但 arr[4]=9 < arr[0]=43 → 不满足环状衔接，非法。 下面给出优化后的 Ja va 实现，时间复杂度 O(n)，空间复杂度 O(1)，逻辑清晰且覆盖了所有边界情况： ```ja va public static boolean isSortedAndRotated(int[] arr) { int n = arr.length; if (n <= 1) return true; int firstPeak = Integer.MIN_VALUE; // 记录拐点左侧的最大值（即原递减序列首元素） // 遍历检查是否至多有一个上升位置 for (int i = 1; i < n; i++) { if (arr[i] > arr[i - 1]) { if (firstPeak != Integer.MIN_VALUE) { return false; // 第二次上升 → 违反递减前提 } firstPeak = arr[0]; // 拐点出现，记录原始首元素 } } // 若无拐点：原数组本身严格递减 → 合法（0次旋转） // 若有拐点：需满足末尾 ≥ 原始首元素，以保证旋转闭环 return firstPeak == Integer.MIN_VALUE || arr[n - 1] >= firstPeak; } ``` **使用示例：** ```ja va System.out.println(isSortedAndRotated(new int[]{10, 9, 44, 43, 11})); // true System.out.println(isSortedAndRotated(new int[]{43, 44, 11, 10, 9})); // false System.out.println(isSortedAndRotated(new int[]{6, 5, 4, 3, 2, 1})); // true（0次旋转） System.out.println(isSortedAndRotated(new int[]{2, 1, 6, 5, 4, 3})); // true（2次顺时针旋转） ``` **注意事项：** - 本方法假设“旋转”指**整体循环位移**，不改变元素相对顺序； - 严格要求“递减”（>，非 >=），所以含重复元素的数组（如 [5,5,4,3,2]）会被判定为 false； - 空数组或单元素数组默认视为合法； - 不需要额外排序或查找最大值，避免了原代码中因索引错位导致的误判（比如对 [43,44,...] 错误定位“最大值位置”）。 这个方案从数学结构出发，一次遍历就能完成验证，既正确又简洁，工程上非常实用。