最大下标距离

努力在北京混出人样

发布于 2019-02-18 15:24:53

9410

发布于 2019-02-18 15:24:53

文章被收录于专栏：祥子的故事

题目 : 给定一个整型数组，找出最大的下标距离j−ij-i，当且仅当A[i]<A[j]A[i]<A[j]和i<ji<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){
      //做下降序列的标记
      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