Учитывая массив A, вычисление B st B [i] хранит ближайший элемент слева от A [i], который меньше, чем A [i].

Question

Учитывая массив A[1..n], мы хотим вычислить другой массив B[1..n] так, чтобы B[i] сохранял ближайший элемент слева от A[i], который меньше A[i].Временная сложность должна составлять O(n).

(для i>1, если слева нет таких более мелких элементов, тогда B[i] просто содержит A[i] и B[1]=A[1].)

Пример:

вход: 6,9,12,17,11
выход: 6,6, 9, 12, 9

Я былподумав о реализации стека,
поместите A[1] в B[1], затем нажмите на стек.
для заполнения B[i], сравните A[i] с элементами стека и выскочит, пока не получите меньший элемент.
наконец нажмите A[i] в стек.

Правильный ли подход выше и есть ли более дешевое решение?

Answer 1

Ваш подход стека правильный. Это работает потому, что если вы добавляете элемент больше A[i], этот элемент никогда не понадобится ни для каких элементов, следующих за A[i], потому что вы можете просто использовать A[i] вместо.

Доступ к каждому элементу возможен только дважды, поэтому O(n).

Answer 2

Не подходит правильный подход к стеку. просто посмотрите, что произойдет, если у вас на входе 6, 9, 12, 17, 11, 15 . Когда вы будете работать с 15, ваш стек был забыт о 12 и 17. Но ближайший маленький левый элемент A [5] равен 12.

Алгоритм Саида тоже не верен. Просто попробуйте вычислить.

Правильный ответ может быть что-то вроде этого

b[1] = a[1];
s[1] = 1;
for (i=2; i<=n; i+=1) { 
  j = i - 1;
  while (j>1){
    if (a[j]<a[i]) {
      b[i] = a[j];
      s[i] = j;
      break;
    } else {
      j = s[j];
    }
  }
  if (j = 1) {
    b[i] = a[j];
    s[i] = j;
  }
}

Я не уверен, но это имеет сложность O (n).

Answer 3

B[1]=A[1]
push(B[1])
for i=2 to n do
{
    while(A[i] > stack_top ANS stack_top!=NULL)
       pop()
    if(stack_top=NULL)
        B[i]=A[i]
    else
        B[i]=stack_top
    push(A[i])
}

Как указывал IVlad, каждый элемент выдвигается и выдвигается не более одного раза, время равно O (n).

Пожалуйста, исправьте меня, если есть какая-то ошибка, и мне любопытно любое альтернативное решение, которое избегает стека и дешевле.