如何重新排列给定整数数组的元素,以便反转每个最大严格升序子数组的元素?
例如,给定数组 { 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]
}
}
最佳答案
我明白你为什么使用嵌套循环了。但我认为你需要跟踪开始和结束,而不仅仅是交换。这是我使用堆栈解决它的方法:
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]
说明
我不断将元素插入堆栈,直到当前元素大于前一个元素。一旦我得到比之前更小的元素,我就会从堆栈中弹出所有元素并将它们写入一个新数组。这种插入和弹出将反转元素。
关于java - 给定一个整数数组,反转每个最大严格升序子数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54777797/