arrays - 面试 - 为每个数组的元素找到更大的元素

Question

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

对于大小为 N 的 unsigned int 的给定数组 arr，对于每个元素(在索引 i 中)我应该返回一个元素在索引 j (j > i) 中，这样 arr[j] > arr[i]IE。我应该返回数组 res，其中 res[i] 有一个 arr[j],j>i,arr[j] > arr[i],j 是所有索引 k 中的最小值，这样 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]);
  }
}