查找大于当前数字的最接近数字的索引

debugcn 发表于 Dev

Shreyas Shetty

对于正整数数组中的每个整数，请找到大于当前整数的最接近整数的索引。同样，我们只需要在当前整数的左侧搜索答案。

例如 -

Input array - [ 5, 4, 3, 6, 2, 3]
Output array - [ -1, 0, 1, -1, 3, 3]

给没有答案的数字指定-1。

有一个简单的O（n ^ 2）方法，对于每个数字，从前一个数字到数组的开头运行一个for循环。

for(int i=0; i<n; ++i)
{
    output[i] = -1;
    for(int j=i-1; j>=0; --j)
    {
        if(input[j] > input[i])
        {
            output[i] = j;
            break;
        }
    }
}

当“ n”较大时，此方法效率不高。有没有更有效的方法？

吉拉德·巴坎（Gilad Barkan）

我相信一种流行的O(n)解决方案是使用堆栈，并保持降序排列（希望该算法从注释的代码中足够清楚）：

function f(A){
  let stack = []
  let output = []

  for (let i=0; i<A.length; i++){
    // While there are lower or
    // equal elements on top of
    // the stack
    while (stack.length && A[ stack[stack.length-1] ] <= A[i])
      stack.pop();
    
    // The next greater element
    // to the left
    if (stack.length)
      output.push(stack[stack.length-1]);
    // There was none
    else
      output.push(-1);

    stack.push(i);
  }

  return output;
}

var As = [
  [5, 4, 3, 6, 2, 3],
  [1, 2, 3, 4, 5],
  [5, 4, 3, 2, 1],
  [0, 3, -1, 5, 4]
];

for (let A of As){
  console.log(`${ A }`);
  console.log(`${ f(A) }`);
  console.log('');
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。