面试 - 为每个数组元素找到更多元素

Question

在采访中我被问到以下问题(不幸的是我找不到比N ^ 2更好的答案)

对于给定的阵列arr为unsigned int的大小N,每个元素(索引i)我应该在索引返回元件j(j> i)中,使得arr[j] > arr[i] 即我应该返回阵列RES其中RES [I]具有ARR [J ],j> i,arr [j]> arr [i],j在所有索引k中都是min,例如arr [k]> arr [i]

arr[] = {3,1,4,2,5,7};
res[] = {2,2,4,4,5,-1};//-1 says no such index

是否有更好的时间复杂性？谢谢

Answer 1

O(N)时间和O(N)空间复杂度:

创建空堆栈,从右侧迭代数组

对于每个迭代项目:只要顶部的项目小于当前项目,就保持从堆栈中弹出,然后如果堆栈变空,则右侧没有更大的元素,如果不是,那么右边第一个更大的项目是当前元素,将当前项目推送到堆栈上

void GetFirstRight(int* arr, int size, int* res){
  stack<int> s;
  for (int i = size - 1; i >= 0; --i) {
    while (!s.empty() && s.top() <= arr[i]) s.pop();
    if (s.empty()) { 
      res[i] = -1;
    } else {
      res[i] = s.top();
    }
    s.push(arr[i]);
  }
}