c++ - 找到比当前数字大的最接近数字的索引

Question

对于正整数数组中的每个整数，找到比当前整数大的最接近整数的索引。此外，我们只需要搜索当前整数左侧的答案。
例如 -

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”很大时，此方法效率低下。有没有更有效的方法？

Answer 1

相信一人气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('');
}