java - 给定一个整数数组，反转每个最大严格升序子数组

Question

如何重新排列给定整数数组的元素，以便反转每个最大严格升序子数组的元素？

例如，给定数组 { 5, 7, 10, 4, 2, 7, 8, 1, 3 }，执行此方法后，数组的元素将为 { 10, 7, 5, 4, 8, 7, 2, 3, 1 }.

我的尝试仅按降序对整数进行排序。如何使这些嵌套循环识别最大严格升序子数组？我相信外循环应该重复找到当前升序序列的末尾，而内循环则反转子数组直到该点。

public class MyClass {
  public static void main(String args[]) {

    int[] arr = {5, 7, 10, 4, 2, 7, 8, 1, 3};

    for (int i=0; i<arr.length-1; i++) {

        if (arr[i] < arr[i+1]) {
            int t = arr[i+1];
            arr[i+1] = arr[i];
            arr[i] = t;
        }
        for (int j=0; j<arr.length-1; j++) {

            if (arr[j] < arr[j+1]) {
                int t = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = t;
            }
        }
    }
    String result = Arrays.toString(arr);
    System.out.println(result); // [10, 8, 7, 7, 5, 4, 3, 2, 1]
  }
}

Answer 1

我明白你为什么使用嵌套循环了。但我认为你需要跟踪开始和结束，而不仅仅是交换。这是我使用堆栈解决它的方法:

public static void main(String[] args) {
    System.out.println(Arrays.toString(reverseAscendingSubArray(new int[]{5, 7, 10, 4, 2, 7, 8, 1, 3})));
}

private static int[] reverseAscendingSubArray(int[] arr) {
    Stack<Integer> stack = new Stack<>();
    int[] result = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        if (i == 0 || arr[i - 1] < arr[i]) {
            stack.push(arr[i]);
        } else {
            for (int j = stack.size(); j > 0; j--) {
                result[i - j] = stack.pop();
            }
            stack.push(arr[i]);
        }
    }
    if (!stack.empty()) {
        for (int j = stack.size(); j > 0; j--) {
            result[arr.length - j] = stack.pop();
        }
    }
    return result;
}

输出

[10, 7, 5, 4, 8, 7, 2, 3, 1]

说明

我不断将元素插入堆栈，直到当前元素大于前一个元素。一旦我得到比之前更小的元素，我就会从堆栈中弹出所有元素并将它们写入一个新数组。这种插入和弹出将反转元素。