java - 找到右边最小的大元素

Question

我正在尝试解决一个算法，其中我必须找到数组右侧的最小大元素 reference

对于下面数组中的一个实例输入:[8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28]

第一个元素 8 右边的最小大元素是 18，第二个元素 58 是 63 等等。我需要逻辑方面的帮助来解决算法。我打算首先用复杂度为 O(n^2) 的蛮力解决。

下面是我写的代码

public class Tmp {

public static void main(String[] args) {

    int[] arr = { 8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28 };
    int[] tmpArr = new int[arr.length];
    int pos = 0;
    int k=0;

    for (int i = 0; i < arr.length-1; i++) { 
        //int next = arr[i];
        for (int j = i + 1; j < arr.length; j++) {
            if ((arr[j] > arr[i])) {
             tmpArr[k]=arr[j]; // take all the values to the right of the element which are greater than it
             k++;
            }
        }

我已经创建了第二个数组 tmpArr 以获取元素右侧大于它的所有值。然后可能对该数组进行排序并取第一个值。但这种逻辑对我来说似乎并不合适。

另一种解决方案可以是

for (int i = 0; i < arr.length-1; i++) { 
    int leastGreater = ? //Don't know what to initialize with
            for (int j = i + 1; j < arr.length; j++) {
                if ((arr[j] > arr[i])) {
                   if(arr[j]<leastGreater){
                 leastGreater = arr[j];
                  }
                }
            }

谁能提供更简单的解决方案？

Answer 1

要解决 O(n log n) 你可以使用 TreeSet 并从右到左。

TreeSet<Integer> set = new TreeSet<Integer>();
for (int i = ar.length - 1; i >= 0; --i) {
    set.higher(ar[i]); // what you need, may be null
    set.add(ar[i]);
}