問題描述

沒什么思路啊，題目如下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.

Example

For sequence = [1, 3, 2, 1], the output should bealmostIncreasingSequence(sequence) = false;

There is no one element in this array that can be removed in order to get a strictly increasing sequence.

For sequence = [1, 3, 2], the output should bealmostIncreasingSequence(sequence) = true.

You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].

Input/Output

[time limit] 4000ms (js)[input] array.integer sequence

Guaranteed constraints:2 ≤ sequence.length ≤ 105,-105 ≤ sequence[i] ≤ 105.

[output] boolean

Return true if it is possible to remove one element from the array in order to get a strictly increasing sequence, otherwise return false.

有個(gè)思路：2層循環(huán)，第一循環(huán)移除元素，第二層循環(huán)判斷移除這個(gè)元素后是否有自增序列。

問題解答

提供一個(gè)思路

作出逐差數(shù)組: 如 a=[1,3,2,1]，逐差后得 [2,-1,-1]

所謂刪除一個(gè)元素，即在在逐差數(shù)組中去頭或去尾，或把相鄰兩個(gè)相加合并成一個(gè)元素。

因此，若逐差數(shù)組中有多于一個(gè)負(fù)數(shù)，則不行; 若無負(fù)數(shù)，則可以; 否則對惟一的負(fù)數(shù)作以上操作，若其能被刪掉或被合并成正數(shù)，則可以

這樣一來，時(shí)間復(fù)雜度可以降到 O(n)

可以在 O(n) 時(shí)間做到:

對每個(gè)相鄰的 [a, b]，判斷是否 a >= b。這樣的數(shù)對破壞嚴(yán)格遞增性。如果這樣的數(shù)對超過一個(gè)，返回false。如果一個(gè)也沒有，返回true。

如果1中只有一對 [a0, b0]，判斷 '移除a0或b0后是否還是遞增' 并返回

結(jié)果是對的，但是超過規(guī)定的時(shí)間了，有更好的方法嗎？

function almostIncreasingSequence(sequence) { var iscan = false; var is = true; var temp for(var i=0;i<sequence.length;i++){is = true;temp = sequence.slice(0,i).concat(sequence.slice(i+1));for(var j=0;j+1<temp.length;j++){ if(temp[j] <= temp[j+1]){is = false;break; }}if(is){ iscan=true; break;} } return iscan;}

時(shí)間復(fù)雜度為O(n)的方法

boolean almostIncreasingSequence(int[] sequence) { if(sequence.length<=2){return true; } //找出逆序的數(shù)的index int count = 0; int biggerIndex = 0; int smallerIndex = 0; boolean isHave = true; for(int i=0;i+1<sequence.length;i++){//如果找到2組逆序，直接返回falseif(count>1){ isHave = false;}if(sequence[i]>=sequence[i+1]){ count ++; biggerIndex = i; smallerIndex = i+1;} }//分別判斷當(dāng)移除2個(gè)數(shù)后剩下的數(shù)組是不是自增的 for(int i=0;i+2<sequence.length;i++){int cur = i;int next = i+1;if(i==biggerIndex){ continue;}if(i+1==biggerIndex){ next = i+2;}if(sequence[cur]>=sequence[next]){ isHave = false;} } if(isHave){return isHave; }else{isHave = true; } for(int i=0;i+2<sequence.length;i++){int cur = i;int next = i+1;if(i==smallerIndex){ continue;}if(i+1==smallerIndex){ next = i+2;}if(sequence[cur]>=sequence[next]){ isHave = false; } } return isHave;}回答4：

這個(gè)是不是統(tǒng)計(jì)逆序數(shù)的個(gè)數(shù)？