Проверить, можно ли заполнить пустые места массива, сохраняя заданные отношения смежных

Опубликовано: 26 Февраля, 2023

Учитывая два массива, массив A[] размера N и массив B[] размера N-1 , массив A имеет все положительные элементы и -1 для пустых значений, а массив B имеет 3 символа {'>', '=', '<'}, что указывает на следующее:

  1. ' > ' означает A[i] > A[i+1]
  2. ' = ' означает A[i] = A[i+1]
  3. ' < ' означает A[i] <A[i+1]

Задача состоит в том, чтобы найти, можем ли мы заполнить -1 (пустые значения) A некоторыми положительными значениями, которые также удовлетворяют отношениям между соседями, упомянутыми в массиве B.

Примеры:

Input: N = 6, A = {8, 6, -1, -1, -1, 11}, B = {‘>’, ‘>’, ‘=’, ‘<‘, ‘>’}
Output: Yes
Explanation: Consider, A becomes {8, 6, 5, 5, 12, 11},  
It satisfies B, so the answer will be ‘Yes’.

Input: N = 5, A = {4, 1, -1, -1, 7}, B = {‘<‘, ‘<‘, ‘<‘, ‘<‘}
Output: No

Подход: Задача может быть решена на основе следующей математической идеи:

Use range to compare whether we can have a valid solution for a particular index and change the range accordingly.

Первоначально левый диапазон равен 0 , а правый диапазон равен INT_MAX.

  • Если встречается оператор '<' , допустимый диапазон для A[i+1] равен левому = A[i]+1 и правому = INT_MAX.
  • Если встречается оператор '>' , допустимый диапазон для A[i+1] равен левому = 0 и правому = A[i] – 1.
  • Если встречается оператор '=' , то допустимый диапазон для A[i+1] равен левому = A[i] и правому = A[i]
  • Значения диапазонов изменяются, когда задано A[i], но когда A[i] = -1, диапазоны сравниваются и изменяются в соответствии с указанными выше условиями.
  • Если для каждой позиции индекса выполняется левое ≤ правое и левое ≥ 0 и правое ≥ 0 , то возвращается «Да», в противном случае возвращается «Нет».

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N)
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ