java - 有什么办法可以让下面的Java代码执行得更快吗？

Question

我的Java代码如下。

boolean almostIncreasingSequence(int[] sequence) {

        Integer[] arr = new Integer[sequence.length];

        for(int ctr = 0; ctr < sequence.length; ctr++) {
            arr[ctr] = Integer.valueOf(sequence[ctr]); // returns Integer value
        }
        System.out.println("Integer :: " + arr);
        List<Integer> al = new ArrayList<Integer>(); 

        // adding elements of array to arrayList. 
        Collections.addAll(al, arr);
        System.out.println("list :: " + al);
        int save, flag = 0;
        for(int i=0; i<al.size(); i++) {
            save = al.get(i);
            al.remove(i);
            if(al.size()==1) return true;
            for(int j=0; j<al.size()-1; j++) {
                if(al.get(j+1) > al.get(j)) {
                    flag = 0;
                    continue;
                }
                else {
                    flag = 1;
                    break;
                }
            }
                if(flag == 0) {
                    return true;
                }
                al.add(i,save);
            }

        if(flag == 1)
            return false;
        return true;
    }

该代码针对一个问题“给定一个整数序列作为数组，确定是否可以通过从数组中删除不超过一个元素来获得严格递增的序列。”

对于某些测试用例，执行此操作需要花费超过 3 秒的时间。但是，我不确定在哪里可以进行更改以更快地执行它。我无权访问测试用例。

在这里，我创建了 2 个 for 循环，因为在第一个循环中，我生成了将删除每个索引的列表，而在第二个循环中，我正在迭代已删除元素的新列表。

像示例数组是 {1,2,4,3} 然后在第一个循环中我创建一个数组，它将是 {2,4,3},{1,4,3},{1,2 ,3} 和 {1,2,4}。在第二个循环中，我迭代所有这 4 个数组来比较每个元素。

Answer 1

主要观察结果是列表可以分解为 3 个(可能是空的)部分:

list = list[0..s) + list[s..e) + list[e..length)

哪里list[0..s)和list[e..length)是严格递增的列表，并且 list[s..e)是介于两者之间的东西。

因为您知道这些前缀和后缀列表是严格递增的，所以您不需要在这些列表中重复检查此属性。

您可以为 s 选择任何值和e受约束0 <= s <= e < length ，但假设您选择它们​​使得 s尽可能大，并且e尽可能小。

如果列表具有所需的整体属性，则:

• s == length ，因此列表已经严格增加，而没有删除任何内容。
• list[s..e)长度最多为 1 ( e-s == 1 )，且 list[0..s) + list[e..length)是严格增加的。您可以通过简单地比较 list[s-1] < list[e] 来检查这一点.
• list[s..e)为空( s == e )，因此您需要 list[0..s-1) + list [e..length) (即删除前缀的最后一个元素)或 list[0..s) + list[e+1..length) (即删除后缀的第一个元素)严格增加。检查(s == 0 || list[s-1] < list[e])和(e+1 == length || list[s] < list[e+1])分别。
• 如果list[s..e)有超过 1 个元素 ( e-s > 1 )，您需要删除多个元素才能为列表提供所需的属性。

查找s和e :

以整数指针 s 开头为零。递增它直到它到达末尾或它指向一个元素，使得 list[0..s)是一个严格递增的列表，但是 list[0..s+1)不会。

以整数指针 e 开头在列表的长度。当 e>s 时递减它和list[e-1..length)不会是一个严格递增的列表。