c++ - 查找所有元素的数组中最新最小元素的位置

Question

对于整数元素数组，我想计算小于该元素的最新元素的位置（如果可能），否则将 -1 存储在该位置。

通过最新元素，我的意思是最大可能的索引小于当前索引。

例如。

（基于 0 索引）

让problem[5] = {4,7,1,3,8}

然后溶胶array = {-1,0,-1,2,3}

现在我能够以 O(n^2) 的时间复杂度做到这一点......但我无法在低于这个时间复杂度的情况下做到这一点。所以，谁能告诉我如何在小于 O(n^2) 的时间复杂度内做到这一点。

我的 n^2 时间复杂度代码：

int n = 5;

int ques[n] = {4, 7, 1, 3, 8};

int sol[n] = { -1, -1, -1, -1, -1};

for (int i = 1; i < 5; i++) {

    int pos;

    for (int j = 0; j < i; j++) {

        pos = -1;

        if (ques[j] < ques[i]) {

            pos = j;

        }

    }

    sol[i] = pos;

}

for (int i = 0; i < n; i++){

    cout << sol[i] << ' ';

}

标签： c++arraysc++14

Answer 1

您可以利用堆栈数据结构，其中包含等待较小前体的元素索引。方法是线性的。

Make a stack `S`

Scan array `Q[]` from the end

   while (Q[i] < Q[S.top()])
        t = S.Pop()
        Sol[t] = i

   Push i onto stack

Write -1 into Sol[] for all indices remaining in the stack   

代码

#include <iostream>
#include <stack>
using namespace std;
int main() {
    int n = 5;
    int ques[] = { 4, 7, 1, 3, 8 };
    int sol[] = { -1, -1, -1, -1, -1 };
    stack<int> s;
    for (int i = n - 1; i >= 0; i--) {
        while (s.size() > 0 && ques[i] < ques[s.top()]) {
            int t = s.top();
            sol[t] = i;
            s.pop();
        }
        s.push(i);
    }
    for (int i = 0; i < n; i++) 
        cout << sol[i] << ' ';