算法 - 具有较小元素的最大左子数组

Question

我正在开发一个程序，在这个程序中，我需要获取整数数组中满足以下条件的元素的索引：该元素右侧的所有元素都大于从索引0到该位置的所有元素。

例如：

第1种情况：已知输入为{5，-2，3，8，6}，那么我需要的索引位置是2（即数组元素值为3的元素），因为索引2之后的所有元素都大于从索引0到索引2的所有元素，即{5，-2，3}。

第2种情况：已知输入为{-5，3，-2，8，6}，那么我需要的索引位置是2（即数组元素值为-2的元素），因为索引2之后的所有元素都大于从索引0到索引2的所有元素，即{-5，3，-2}。

下面是我的Java程序：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class ArrayProgram {

    public static void main(String[] args) {
        int[] array1 = { 5, -2, 3, 8, 6 };
        int[] array2 = { -5, 3, -2, 8, 6 };
        process(array1);
        process(array2);
    }

    private static void process(int[] array) {
        List<Integer> list = new ArrayList<Integer>();
        int maxIndex = 0;
        list.add(array[0]);
        System.out.println(Arrays.toString(array));
        for (int i = 1; i < array.length; i++) {
            if (array[i] <= Collections.max(list)) {
                list.add(array[i]);
                maxIndex = i;
            }
        }

        System.out.println("index = " + maxIndex + ", element = " + array[maxIndex]);
    }
}

程序输出为：

[5, -2, 3, 8, 6]
index = 2, element = 3
[-5, 3, -2, 8, 6]
index = 0, element = -5

它适用于情况1，但对于情况2失败了。您能帮我修复这个问题吗？是否有其他更好的解决方法？

- learner

---

这个算法没有正常工作。你是自己发明的还是来自其他网站？ - ByeBye

因为你需要计算所有可能性，我建议将其存储在一个映射中，并在最后获取最小值。 - azro

在 array2[0] 中的值为 -5（负数）。在您的第二个示例中，值为 5（正数）。因此，您的程序似乎工作正常（因为索引 1 > 索引 0 的值）。 - Stefan Warminski

在第二种情况下，数组以5开头，在代码中，数组2以-5开头。 - Arun Sudhakaran

但是算法仍然没有起作用。 - ByeBye

Answer 1

很遗憾，您的解决方案存在几个逻辑错误。其中一个反例：[2, 1, 3, 6, 5]（您的算法返回索引1，但正确答案是2）。

我提出了另一种时间复杂度为O(n)的解决方案：

1. 从左到右迭代计算[0..i]区间内元素的最大值。
2. 从右到左迭代计算[i+1..n]区间内元素的最小值，并将此最小值与第一步先预先计算出的左侧元素的最大值进行比较。

样本实现如下：

static void process(int[] array) {
    int n = array.length;
    if (n < 2) return;

    int[] maxLeft = new int[n];
    maxLeft[0] = array[0];
    for (int i = 1; i < n; ++i) {
        maxLeft[i] = Math.max(maxLeft[i-1], array[i]);
    }  

    int minRight = array[array.length-1];
    for (int i = n-2; i >= 0; --i) {
        if (maxLeft[i] < minRight) {
            System.out.println("index = " + i + ", element = " + array[i]);
            return;
        } 
        minRight = Math.min(minRight, array[i]); 
    }
}    

可运行的代码示例：http://ideone.com/mmfvmH

- DAle

---

只需要在分区是第（n-2）个元素的情况下添加打印语句，例如int[] array1 = { 3，-2，3，-2，3 }; - Hakes

@Hakes，但是这个问题没有答案。从问题来看：“我需要获取整数数组中元素的索引，使得该索引位置右侧的所有元素都大于该索引位置左侧0到该位置的所有元素”。 - DAle

是的，你说得对，应该是大于，而不是大于等于，我的错误。 - Hakes

@DAle，谢谢。你能否推荐一本好的算法书给我？我尝试过从《算法导论》学习，但是我无法理解其中的内容。 - learner

@user3181365，不客气！《算法导论》是一本很棒的书，曾经是我的个人选择。也许一些Robert Sedgewick或Niklaus Wirth的书对你有帮助。 - DAle

Answer 2

我把我的评论改成了答案。从数组的末尾开始，右侧只有一个元素，左侧有n-1个元素。然后检查左侧的最大值是否小于右侧的最小值，如果满足条件，则完成，否则将索引向左移动并再次检查。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class ArrayProgram {

    public static void main(String[] args) {
        int[] array1 = { 5, -2, 3, 8, 6 };
        int[] array2 = { -5, 3, -2, 8, 6 };
        int[] array3 = { 1, 3, 5, 8, 4 };
        int[] array4 = { 1, 1, 1, 1, 1 };
        process(array1);
        process(array2);
        process(array3);
        process(array4);
    }


    private static void process(int[] array) {
        List<Integer> listLeft = new ArrayList<Integer>();
        List<Integer> listRight = new ArrayList<Integer>();

        //create an array that consists upto n-1 elements
        int arraySize = array.length;
        if ( arraySize < 2){
            System.out.println("None");
            return;
        }
        for ( int i = 0; i < arraySize - 1; i++){
            listLeft.add ( array[i]);
        }
        //create an array that has the last element
        listRight.add ( array[arraySize - 1]);

        //iterate from the last adding new elements till the condition satisfies
        for ( int i = arraySize - 2; i >= 0; i--){

            //if the condition is satisfied exit
            if ( Collections.max(listLeft) < Collections.min(listRight)){
                System.out.println("index = " + i + ", element = " + array[i]);
                return;
            }else{
                //remove an element from left and add an element to right
                listLeft.remove (listLeft.size() - 1);
                listRight.add ( array[i]);
            }
        }

        System.out.println("None");
    }
}

- Hakes

Answer 3

我建议使用一种算法来获取正确的输出。它将在O(n)时间内执行。假设arr[]中有n个元素。维护两个数组int minElementIndex[]和maxElementIndex[]。

• minElementIndex[i]存储子数组[(i+1) ... (n-1)]中存在的最小值元素的索引。当i=n-1时，minElementIndex[n-1]=n-1
• maxElementIndex[i]存储子数组[0 ... (i)]中存在的最大值元素的索引。当i=0时，maxElementIndex[0]=0

填充minElementIndex[0...n-1]的代码：

int index=minElementIndex[n-1];
for(int i=n-2;i>=0;i--){
  minElementIndex[i] = index;
  if(arr[i]<arr[index])
      index=i;
}

填充maxElementIndex[0 ... n-1]的代码：

int index=maxElementIndex[0];
for(int i=1;i<n;i++){
  if(arr[i]>arr[index])
     index=i;
  maxElementIndex[i]=index;
}

现在，只需按照以下方式迭代两个数组即可：

for(int i=1;i<n-1;i++){ 
    if(arr[maxElementIndex[i]]< minElementIndex[i]){
        System.out.println(i);
    }
}

让我们对所提出的算法进行干运行。

情况1： arr [5] = {5，-2，3，8，6} minElementIndex [5] = {1,2,4,4,4} 和maxElementIndex [5] = {0,0,0,3,3} 。显然在i=2时，arr[maxElementIndex[i]]<arr[minElementIndex[i]]，即5 < 6

情况2： arr [5] = {-5，3，-2，8，6} minElementIndex [5] = {2,2,4,4,4} 和maxElementIndex [5] = {0,1,1,3,3} 。显然在i=2时，arr[maxElementIndex[i]]<arr[minElementIndex[i]]，即3 < 6

- Shubham Agrawal