一道简单算法题求助

Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.
写一个方法， 判断一个 给定的 int  数组（长度 > 2）   能不能从数组中去除一个int，使这个新数组 严格递增。


比如 数组位 【1，3，2，1】 , 不能出去一个元素 使数组 严格递增，返回false；
数组【1，3，2】，除去一个元素 可得【1，3】，或者【1，2】， 可以严格递增，返回true；


我的解法：
boolean almostIncreasingSequence(int[] sequence) {


            if(sequence.length ==2 ){
                return true;
            }
            
            boolean result = true;
                        
            for(int i = 0; i<sequence.length; i++){
                result = true;
                int [] arr = Arrays.copyOf(sequence, sequence.length);
                System.arraycopy(arr, i+1 , arr , i, sequence.length-1-i);
                for(int j = 0; j < arr.length -2; j++){
                     if(arr[j] >= arr[j+1]){
                         result = false;
                         break;   
                     }
                }
                
               if(result) break;
            }
            
            return result;
}


虽然结果对，但是超时。请问有没有好的解法？

回头看了一眼， 竟然讨论如此激烈。。 意外。。

几个想法

1) op的答案有点看不懂， 如果有解释最好了。
2) 用 LIS的解法应该没问题， 是nlgn的速度，就看LIS的长度是不是 >= length - 1即可
3) 用dp解, dp[i, j] = true if sequence[i to j] is strictly increasing。 但是这个应该是n方，毕竟每一个点都得走一遍， 不知道是不是太慢

1. boolean almostIncreasingSequence(int[] sequence)
   
2.     {
   
3.         int n = sequence.length;
   
4.         f = new Boolean[n][n];
   
5.         for(int i = 0; i < n; i++)
   
6.             f[i][i] = true;
   
7.         dp(sequence, 0, n - 1);
   
8.         // for(Boolean[] ff : f)
   
9.         //     System.out.printf("%s \n", Arrays.toString(ff));
   
10.         for(int i = 1; i < n - 1; i++)
    
11.             if(f[0][i - 1] != null && f[i + 1][n - 1] != null && f[0][i -1]
    
12.                 && f[i + 1][n - 1] && sequence[i - 1] < sequence[i + 1]) return true;
    
13.         return false;
    
14.     }
    
15. 
    
16.     Boolean[][] f;
    
17. 
    
18.     boolean dp(int[] seq, int left, int right)
    
19.     {
    
20.         // System.out.printf("%d %d \n",left, right);
    
21.         if(left == right) return f[left][right] = true;
    
22.         if(left + 1 == right) return f[left][right] = seq[left] < seq[right];
    
23.         if(f[left][right] != null) return f[left][right];
    
24.         boolean res = false;
    
25.         for(int i = left; i < right; i++)
    
26.         {
    
27.             boolean li = dp(seq, left, i), ri = dp(seq, i + 1, right);
    
28.             res |= seq[i] < seq[i + 1] && li && ri;
    
29.         }
    
30.         return f[left][right] = res;
    
31.     }
    

复制代码

4) 用单一解， 这个不太成熟。。基本就是说可以退后一次。 因为如果可以变成strictly increasing的话，就代表可以往回撤一次。

1.     boolean almostIncreasingSequence(int[] sequence)
   
2.     {
   
3.         boolean f = false;
   
4.         for(int i = 1, j = 0; i < sequence.length; i++)
   
5.         {
   
6.             // System.out.printf("%d %d \n", i, j);
   
7.             if(sequence[j] < sequence[i]) j++;
   
8.             else
   
9.             {
   
10.                 j--;
    
11.                 // j too big | too small
    
12.                 if(f) return false;
    
13.                 f = true;
    
14.             }
    
15.         }
    
16.         return true;
    
17.     }   

复制代码

受版上大牛门的启发， 特别是randrand1  大侠的解法，自己想出来了一个双检查法： 终于通过了。非常感谢大侠们的帮助。
public class AlmostIncreasingSequnece {
       
    boolean almostIncreasingSequence(int[] s) {
                int index = -1;                               
               
                for(int i =1; i<s.length; i++) {
                        if(s[i-1]>= s[i]) {
                                index = i;
                                break;
                        }
                }
               
                if(index == -1) return true;                 
                return check(s, index);                    
        }
   
        boolean check(int [] a, int index) {
                 for(int i = index; i< a.length-1 ; i++) {
                         if(a[i]>= a[i+1]) return false;
                 }       
                 boolean flag1 = true;
                 boolean flag2 = true;
                 
                 //Double check! remove a[index]  and a[index-1]
                 // Need to remove a[index] check if a[index-1]>=a[index+1]
                 // and  to remove a[index-1] check if a[index-2]>=a[index]                  
                 // If either condition is true, return true.
                 if(index >1 && index<a.length-1) {
                         if(a[index-2]>= a[index])flag1 = false;
                         if(a[index-1]>=a[index+1]) flag2 = false;
                 }
                           
                 return (flag1 || flag2);                 
         }
}

1. 
   
2. public class IncreasingSeq {
   
3.         public static void main(String [] args) {
   
4.                 System.out.println(aISeq(new int[] {1,2,3,4,5,6,3,4,9}) == false);
   
5.                 System.out.println(aISeq(new int[] {1,2,3,4,5,6,4,9}) == true);
   
6.                 System.out.println(aISeq(new int[] {1,2,7,3,4}) == true);
   
7.                 System.out.println(aISeq(new int[] {1,2,7,3,4,3,4}) == false);
   
8.                 System.out.println(aISeq(new int[] {1,2,7,6,3,4,}) == false);
   
9.                 System.out.println(aISeq(new int[] {1,2,3}) == true);
   
10.                 System.out.println(aISeq(new int[] {1,3,2}) == true);
    
11.                 System.out.println(aISeq(new int[] {1,2,3,4,5,6,0,7}) == true);
    
12.         }
    
13.        
    
14.         public static boolean aISeq(int[] A){
    
15.                 boolean adj = false;
    
16.                 int count = 0;
    
17.                 for(int i = 1;i<A.length;i++) {
    
18.                         int gap = A[i]-A[i-1];
    
19.                         count+= gap;
    
20.                         if(count < i-1 || gap<=0) {
    
21.                                 if(adj) return false;
    
22.                                 else {
    
23.                                         adj = true;
    
24.                                 }
    
25.                         }       
    
26.                 }
    
27.                 return true;
    
28.         }
    
29. }
    

复制代码

也来说一下自己的思路？
首先这是一个int array，如果数列严格递增的话，A[i]-A[i-1] >=1, 那么考虑sum of A[i]-A[i-1], 在任何时候一定>=i
如果中间有最多一位非严格递增的话，那么设A’ 为删除A中某element之后A'严格递增，原数列sum of A[i]-A[i-1],  少算一个元素，在任何时候一定>=i-1
在某位非严格递增可以用A[i]-A[i-1] <=0 判定
然后如果两次违反上述规律return false就可以了，其它情况return true

你的解法时间复杂度是多少？

直接遍历一遍看是否有降序的情况， 超过一次就是不符合咯 ？  复杂度o（n）

其实可以扫一遍，关键点就是在用两个变量标记最大值，第二大值

遍历，每次比较当前和后一个数，找到一个或没有非递增的数对返回true，如果还能找到第二个就是false，不知道对不对

力扣315，会做这个应该也没问题

或者是算increasing subsequence的长度== n-1？

返回false的条件: array中有两个value满足a1 <= a2 >= a3，相当于找peak value，感觉可以用binary search的方法，O(lgn)，不知道可不可行

上面的解法都偏复杂了，可以简单想一下。如果在数组里面找不满足a[i-1] <= a[i]的pair，有两种情况，第一种情况是找不到，也就意味着原来的数组是排好序的。
第二个情况是至少可以找到一个，假设这个pair是a[idx-1] > a[idx], 可以有的操作也就是删掉一个数字，那么就是要么得删掉a[idx-1]，要么删掉a[idx]，如果两种情况删掉，数组都不是排好序的，那么就得return false

1. /* package whatever; // don't place package name! */
   
2. 
   
3. import java.util.*;
   
4. import java.lang.*;
   
5. import java.io.*;
   
6. 
   
7. /* Name of the class has to be "Main" only if the class is public. */
   
8. class Ideone {
   
9. static boolean IgnoreIdxCheck(int[] sequence, int idx) {
   
10.   int prev = Integer.MIN_VALUE;
    
11.   for (int i = 0; i < sequence.length; ++i) {
    
12.    if (i == idx) continue;
    
13.    if (sequence[i] < prev) return false;
    
14.    prev = sequence[i];
    
15.   }
    
16.   return true;
    
17. }
    
18. static boolean almostIncreasingSequence(int[] sequence) {
    
19.   int idx = -1;
    
20.   for (int i = 1; i < sequence.length; ++i) {
    
21.    if (sequence[i] < sequence[i - 1]) {
    
22.     idx = i;
    
23.     break;
    
24.    }
    
25.   }
    
26.   if (idx == -1) return true;
    
27.   return IgnoreIdxCheck(sequence, idx - 1) || IgnoreIdxCheck(sequence, idx);
    
28. }
    
29. 
    
30. public static void main(String[] args) throws java.lang.Exception {
    
31.   System.out.println(almostIncreasingSequence(new int[] {
    
32.    1,
    
33.    4,
    
34.    2
    
35.   }) == true);
    
36.   System.out.println(almostIncreasingSequence(new int[] {
    
37.    1,
    
38.    3,
    
39.    2,
    
40.    1
    
41.   }) == false);
    
42. }
    
43. }

复制代码

补充内容 (2018-5-22 04:58):
楼主的算法是O(N^2)，我提供的这个是O(N)，第二句话有点问题， "如果在数组里面找不满足a[i-1]> a[i]的pair"

补充内容 (2018-5-22 05:00):
没认真看，题目要求strick 递增，这个代码有点问题

randrand1 发表于 2018-5-22 04:48
上面的解法都偏复杂了，可以简单想一下。如果在数组里面找不满足a  a, 可以有的操作也就是删掉一个数字，那 ...

没认真看，题目要求strick 递增，这个代码有点问题