Найдите индекс ближайшего числа, который больше текущего числа

Question

Для каждого целого числа в массиве положительных целых чисел найдите индекс ближайшего целого числа, которое больше текущего целого числа. Кроме того, нам нужно искать ответ только слева от текущего целого числа.

Например -

Input array - [ 5, 4, 3, 6, 2, 3]
Output array - [ -1, 0, 1, -1, 3, 3]

Присвойте -1 тем числам, на которые нет ответа.

Существует простой метод O (n ^ 2), для каждого числа запускайте a для l oop от предыдущего числа до начала массива.

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('');
}

Answer 2

Предлагаемый ответ является адаптацией: https://www.geeksforgeeks.org/find-the-nearest-smaller-numbers-on-left-side-in-an-array/

Основная идея - использовать стек для запоминания обработанного значения. В ссылке они заботятся о значении, но его можно легко адаптировать для выходных индексов.

#include <iostream>
#include <vector>
#include <stack>

std::vector<int> function(std::vector<int> input) {
    std::vector<int> output;
    output.reserve(input.size());

    // Create an empty stack 
    // first element of the pair is the index. second is the value
    std::stack<std::pair<int,int>> S; 
  
    // Traverse all array elements 
    for (int i=0; i<input.size(); i++) 
    { 
        // Keep removing top element from S while the top 
        // element is less than or equal to arr[i] 
        while (!S.empty() && S.top().second <= input[i]) 
            S.pop(); 
  
        // If all elements in S were greater than arr[i] 
        if (S.empty()) 
            output.push_back(-1);
        else  //Else print the nearest smaller element
            output.push_back(S.top().first);

  
        // Push this element 
        S.push({i, input[i]}); 
    } 
    
    return output;
}

int main() {
    std::vector<int> input{5, 4, 3, 6, 2, 3};
    std::vector<int> output = function(input);

    for(int index : output) {
        std::cout << index << ' ';
    }

    return 0;
}

Вывод:

-1 0 1 -1 3 3

Проводник компилятора: https://godbolt.org/z/8W3ecv