Учитывая массив целых чисел, инвертируйте каждый максимальный строго восходящий подмассив - PullRequest
Новая
       8

Учитывая массив целых чисел, инвертируйте каждый максимальный строго восходящий подмассив

0 голосов
/ 20 февраля 2019

Как бы я переставил элементы заданного массива целых чисел так, чтобы элементы каждого максимального строго восходящего подмассива были инвертированы?

Например, учитывая массив {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]
  }
}

1 Ответ

0 голосов
/ 20 февраля 2019

Я понимаю, почему вы используете вложенный цикл.Но я думаю, что вам нужно отслеживать начало и конец, а не просто поменяться местами.Вот как я решил это с помощью стека: 

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]

Объяснение

Я продолжаю толкатьэлементы в стек, пока текущий элемент не станет больше предыдущего.Как только я получаю что-то меньшее, чем предыдущий, я извлекаю все элементы из стека и записываю их в новый массив.Это нажатие и выталкивание перевернут элементы.

...