本文首發(fā)為CSDN博客捧颅，地址為：http://blog.csdn.net/xxzhangx/article/details/53505867
歡迎關(guān)注景图，謝謝！引用轉(zhuǎn)載請注明作者和地址碉哑！
題目 : 給定一個整型數(shù)組挚币，找出最大的下標(biāo)距離j-i扣典，當(dāng)且僅當(dāng)A[i]<A[j]和i<j。
偽代碼
int maxIndexDistance(int A[]){
if (A==null || A.length<2) return 0;
boolean inDescSeq[] = new boolean[A.length];
int min = A[0],n=A.length;
inDescSeq [0] = true;
for(int i = 1;i <n;i++){
if(A[i] < min){
//做下降序列的標(biāo)記
inDescSeq[i] = true;
min = A[i];
}
}
int maxDist = 0,i=n-1,j=n-1;
while(i>=0){
if (inDescSeq[i] == false){
i--; //倒序找出下一個降序列的元素
continue;
}
while ((A[j] <= A[i]) && (j>i))
j --; //從后往前移動直至找到符合的元素
if((j-i) > maxDist){
maxDist = j-i;
}
i--;
}
return (maxDist);
}
R語言
maxIndexDistance<-function(a)
{
if (is.null(a) || length(a) < 2)
{
return (0)
}
inDescSeq = rep('FALSE',length(a))
min = a[1];n=length(a)
inDescSeq[1] = 'TRUE'
for(i in 2:length(a))
{
if(a[i] < min)
{
inDescSeq[i] = 'TRUE'
min = a[i]
}
}
maxDist =0;i = n;j=n;
while(i >= 1)
{
if(inDescSeq[i] == 'FALSE')
{
i = i -1;
}
while ((a[j] <= a[i]) && (j > i))
{
j = j-1
}
if ((j-i) > maxDist)
{
maxDist = j-i
}
i = i -1
}
return(maxDist)
}
#1
> a<-c(1:20,30:14,2:23,54:33)
> maxIndexDistance(a)
[1] 59
#2
> a<-c(5,3,4,0,1,4,1)
> maxIndexDistance(a)
[1] 4
