O (N) Алгоритм
- Инициализировать выходной массив для всех -1 с.
- Создать пустой стек индексов элементов, которые мы посетили во входном массиве, но нееще знаю ответ для в выходном массиве.
- Перебираем каждый элемент во входном массиве:
- Это меньше, чем элемент, индексированный вершиной стека?
- Да.Это первый такой элемент, который будет таким.Заполните соответствующий элемент в нашем выходном массиве, удалите элемент из стека и попробуйте снова, пока стек не станет пустым или ответ будет отрицательным.
- Нет.Перейдите к 3.2.
- Добавьте этот индекс в стек.Продолжите итерацию с 3.
Реализация Python
def find_next_smaller_elements(xs):
ys=[-1 for x in xs]
stack=[]
for i,x in enumerate(xs):
while len(stack)>0 and x<xs[stack[-1]]:
ys[stack.pop()]=x
stack.append(i)
return ys
>>> find_next_smaller_elements([4,2,1,5,3])
[2, 1, -1, 3, -1]
>>> find_next_smaller_elements([1,2,3,4,5])
[-1, -1, -1, -1, -1]
>>> find_next_smaller_elements([5,4,3,2,1])
[4, 3, 2, 1, -1]
>>> find_next_smaller_elements([1,3,5,4,2])
[-1, 2, 4, 2, -1]
>>> find_next_smaller_elements([6,4,2])
[4, 2, -1]
Объяснение
Как это работает
Это работает, потому чтовсякий раз, когда мы добавляем элемент в стек, мы знаем, что его значение больше или равно каждому элементу в стеке.Когда мы посещаем элемент в массиве, мы знаем, что если он меньше, чем любой элемент в стеке, он должен быть ниже, чем последний элемент в стеке, поскольку последний элементдолжен быть самым большим.Таким образом, нам не нужно выполнять какой-либо поиск в стеке, мы можем просто рассмотреть последний элемент.
Примечание. Вы можете пропустить шаг инициализации, если добавите последний шаг для очистки стека.и использовать каждый оставшийся индекс, чтобы установить соответствующий элемент выходного массива в -1.В Python проще инициализировать его до -1 с при его создании.
Сложность времени
Это O (N).Основной цикл явно посещает каждый индекс один раз.Каждый индекс добавляется в стек ровно один раз и удаляется не более одного раза.
Решение в виде вопроса для интервью
Этот вопрос может быть довольно пугающим в интервью, но я бы хотелОтметьте, что (надеюсь) интервьюер не ожидает, что решение возникнет из вашего ума полностью сформированным.Обсудите их через ваш мыслительный процесс.У меня получилось что-то вроде этого:
- Есть ли какая-то связь между позициями чисел и их следующим меньшим числом в массиве?Знание некоторых из них ограничивает возможности других?
- Если бы я стоял перед доской, я бы, вероятно, набросал примерный массив и нарисовал линии между элементами.Я мог бы также нарисовать их в виде двухмерной гистограммы - горизонтальная ось - это позиция во входном массиве, а вертикальная ось - это значение.
- У меня была догадка, что это показало бы образец, но бумаги не было в руках.Я думаю, что диаграмма сделает это очевидным.Подумав об этом тщательно, я увидел, что линии не будут произвольно перекрываться, а будут только гнездиться.
- В этот момент мне пришло в голову, что это невероятно похоже на алгоритм, который Python использует внутри для преобразования отступа вINDENT и DEDENT виртуальные токены, о которых я читал раньше.Смотрите "Как компилятор разбирает отступ?"на этой странице: http://www.secnetix.de/olli/Python/block_indentation.hawk Однако до тех пор, пока я действительно не разработал алгоритм, я продолжил эту мысль и определил, что на самом деле он такой же, поэтому я не думаю, что он слишком сильно помог,Тем не менее, если вы видите сходство с какой-то другой проблемой, которую вы знаете, вероятно, стоит упомянуть об этом и сказать, как она похожа и чем она отличается.
- Отсюда общая форма основанной на стекеАлгоритм стал очевидным, но мне все еще нужно было подумать об этом немного больше, чтобы убедиться, что он будет работать нормально для тех элементов, у которых нет последующих меньших элементов.
Даже если вы не придумалирабочий алгоритм, попробуйте дать интервьюеру понять, о чем вы думаете.Зачастую им интересен не только ответ, но и мыслительный процесс. Для сложной проблемы неспособность найти лучшее решение, но показать понимание проблемы может быть лучше, чем знание готового ответа, но неспособность дать ему много.анализ.