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

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]

说明

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

Answer 2

您可以按照下面的代码尝试使用冒泡排序。

public static void reverseAscendingSubarrays(int[] items){
        int start = -1;
        int stop = -1;
        for (int i = 0; i < items.length; i++){
            if (i != items.length - 1){
                if (items[i] <= items[i + 1]){
                    if (start == -1) {
                        start = i;
                    }
                }
                else {
                    if (start != -1) {
                        stop = i;
                    }
                }
            }
            else{
                if (start != -1){
                    stop = i;
                }
            }
            if (start != -1 && stop != -1){
                //sort array from start to stop (uses bubble sort - inefficient for large arrays)
                for (int n = 0; n < stop - start + 1; n++)
                    for (int j = start; j < stop; j++){
                        if (items[j] < items[j+1]){
                            //swap
                            int temp = items[j];
                            items[j] =items[j+1];
                            items[j+1] = temp;
                        }
                    }
                start = -1;
                stop = -1;
            }
        }
    }

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

Given an array of integers, reverse every maximal strictly ascending subarray

java

arrays

for-loop

nested-loops