如何在Java中判断数组是否为降序排序后顺时针旋转的数组？

问题描述 #

我们需要实现一个方法，判断给定数组是否由降序排序的数组顺时针旋转至少1次得到：

• 合法示例：原降序数组44 43 11 10 9顺时针旋转2次得到10 9 44 43 11，应返回Yes；旋转2次的降序数组6 5 4 3 2 1得到2 1 6 5 4 3，应返回Yes
• 非法示例：数组[43 44 11 10 9]无法由降序数组旋转得到，应返回No；未旋转的纯降序数组6 5 4 3 2 1，应返回No

现有代码存在缺陷，会错误地将[43 44 11 10 9]判断为合法，需要优化。

现有代码的核心问题 #

1. 缺失关键结构验证：未检查旋转后的数组是否符合降序数组的旋转逻辑——后半段的最后一个元素必须大于等于前半段的第一个元素（原降序数组中，前半段是原数组的末尾部分，后半段是原数组的开头部分，原数组末尾的前一个元素必然≥末尾第一个元素）。
2. 最大值索引判断不严谨：仅记录第一个大于当前最大值的元素位置，若存在多个相同最大值，可能导致分割点错误。

修复后的代码 #

import java.util.Scanner;

class Main {

    public static boolean isRotatedDescendingArray(int arr[]) {
        int n = arr.length;
        // 长度<=1的数组无法通过旋转得到不同结果，直接返回No
        if (n <= 1) {
            return false;
        }

        int max = Integer.MIN_VALUE;
        int maxIndex = 0;
        // 记录最后一个最大值的索引，确保分割点符合旋转结构
        for (int i = 0; i < n; i++) {
            if (arr[i] >= max) {
                max = arr[i];
                maxIndex = i;
            }
        }

        // 最大值在首位，说明是未旋转的降序数组或全相同元素，返回No
        if (maxIndex == 0) {
            return false;
        }

        // 检查前半段（0到maxIndex-1）是否非递增
        for (int i = 0; i < maxIndex - 1; i++) {
            if (arr[i] < arr[i + 1]) {
                return false;
            }
        }

        // 检查后半段（maxIndex到n-1）是否非递增
        for (int i = maxIndex; i < n - 1; i++) {
            if (arr[i] < arr[i + 1]) {
                return false;
            }
        }

        // 关键验证：后半段最后一个元素 >= 前半段第一个元素
        if (arr[n - 1] < arr[0]) {
            return false;
        }

        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testCases = sc.nextInt();
        for (int t = 0; t < testCases; t++) {
            int size = sc.nextInt();
            int arr[] = new int[size];
            for (int j = 0; j < size; j++) {
                arr[j] = sc.nextInt();
            }
            System.out.println(isRotatedDescendingArray(arr) ? "Yes" : "No");
        }
        sc.close();
    }
}

代码说明 #

1. 边界处理：长度≤1的数组直接返回No，因为旋转后与原数组一致，不符合“旋转”要求。
2. 最大值索引修正：记录最后一个最大值的位置，确保分割点对应旋转后的数组结构。
3. 非递增检查：验证前半段和后半段均保持降序（允许元素相等）。
4. 关键逻辑验证：通过arr[n-1] >= arr[0]确保数组符合降序旋转后的结构，过滤掉非法案例。
5. 语义化命名：将方法重命名为isRotatedDescendingArray，提高代码可读性。

测试用例验证 #

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