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

Question

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

对于大小为N的无符号整数数组arr，对于每个元素（在索引i中），我应该返回索引j（j>i）中的一个元素，使得arr[j] > arr[i]。也就是说，我应该返回一个数组res，在其中res[i]具有一个arr[j]，j>i，arr[j]>arr[i]，其中j是所有满足arr[k] > arr[i]的索引k中最小的一个。 例如：

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

有没有更好的时间复杂度的方案呢？ 谢谢。

- YAKOVM

---

你能不能先对数组进行排序，然后再查看下一个元素呢？任何执行时间小于N^2的排序算法都可以。 - Vaughan Hilts

你的例子中res[]有缺陷。你说res[i]包含arr[j]。然而，你有arr[0] = 3和res[0] = 2，但是2 < 3。编辑：算法贪心不能用于最小索引。 - Shashank

元素是否可以重复出现，还是必须唯一？ - Ron Teller

http://www.geeksforgeeks.org/next-greater-element/ - Bernhard Barker

@Dukeling "应该返回数组 res，其中 res[i] 包含 arr[j]" - Michal

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]);
  }
}

- Michal

---

我认为这不是O(n)。你有两个嵌套循环。 - Abhishek Bansal

让我们来分析一下：在一个函数调用中，内部循环会迭代多少次？答案是：最大迭代次数是size的值。我们只插入一次项目。 - Michal

但是在弹出元素时，我觉得你可能会失去那些对未来元素很重要的项目。 - Abhishek Bansal

没错，当你到达8时，在8左边的任何元素中，都不会在res数组中有7，因此7甚至更早地被弹出-当我们到达8时。 - Michal

是的，你说得对。我误读了问题，把min(arr[j])看成了min(j)。+1 :) - Abhishek Bansal

Answer 2

O(n)算法：

维护一个仍未解决的索引堆栈，这个堆栈将被排序，以便最小的仍未解决的值位于顶部。当您到达一个新元素时，从堆栈中弹出，直到新元素的值小于堆栈顶部的值。对于每个弹出的值，答案是当前索引。然后将当前索引推入堆栈。最后，任何仍在堆栈上的结果为-1。

代码（C ++）：

stack<int> unsolved;
int arr[] = {3,1,4,2,5,7}, N = 6;
int res[1234];

int main() {
    for (int i = 0; i < N; i++) {
        while (!unsolved.empty() && arr[unsolved.top()] < arr[i]) {
            res[unsolved.top()] = i;
            unsolved.pop();
        }
        unsolved.push(i);
    }
    while (!unsolved.empty()) {
        res[unsolved.top()] = -1;
        unsolved.pop();
    }
    // Print results
    for (int i = 0; i < N; i++) printf("%d%c", res[i], i==N-1 ? '\n' : ' ');

    return 0;
}

输出：

2 2 4 4 5 -1

- Abyss

---

我认为这不是O(n)。你有两个嵌套的循环。 - Abhishek Bansal

这是一种非常简单的分析时间复杂度的方法。如果你仔细想想，每个元素只被推入一次，每次内部循环运行时一个元素被弹出，因此它最多只会运行N次。 - Abyss

是的，你说得对。我把问题理解成了min(arr[j])而不是min(j)。+1 :) - Abhishek Bansal

Answer 3

保持一个平行数组b。使b [0] = 0。 运行迭代遍历a的元素。在进行操作时，将b的值设置为a的连续单元格之间的差异。

因此，如果

a[0]=9
a[1]=4
a[2]=17
a[3]=2
a[4]=3
a[5]=6
a[6]=0
a[7]=3
a[8]=1
a[9]=1
a[10]=7

然后，

b[0]=0
b[1]=-5
b[2]=13
b[3]=-15
b[4]=1
b[5]=3
b[6]=-6
b[7]=3
b[8]=-2
b[9]=0
b[10]=6

你需要关注的是数组b中的负数单元格。 现在，从上面的示例中的b [10]开始向后迭代数组b。 保持一个currentMax值。最初设置为数组中第一个最大的正数-对于数组末尾的负数条目，你无能为力。 当你从b [b.length]向下迭代到b [0]时，请执行以下操作： 更新currentMax：

currentMax += <value at the current cell of **b**>

如果(currentMax<0)，那么/*你已经到达没有索引的元素*/继续寻找正数b[i]的条目，当找到一个时，将currentMax的值设置为它。

currentMax的(+)值表示重置currentMax的单元格是所有已访问单元格的索引，(-)值表示无索引单元格。

在上面的例子中，a[10]处的7是a[3]..a[9]中所有元素的索引，因为 -currentMax是在单元格10初始化的(之后没有重置) -所有这些加法之后，currentMax的值一直是(+)一直到单元格4(单元格4反映了从单元格3到4的变化)

在 b[3]，currentMax 下降到 0 以下-- 意味着单元格 2 没有索引。 在 b[2] 找到的值为正数，而 currentMax 为负数-- 因此在 b[3] 上进行，currentMax=13 并迭代。

数组大小线性 -- 需要 O(n) 时间。

- ashley