Как проверить, можно ли удалить не более одного элемента из списка, чтобы он был строго возрастающим?
Решаю задачу: дан список, надо проверить, можно ли удалить не более одного элемента из него, чтобы он был строго возрастающим? Как я решил: чувствую, что есть какой-то алгоритм однократного прохождения по списку в цикле, но не понимаю, как его реализовать. В итоге я в цикле удаляю по одному элементу и новый список без этого элемента просто проверяю, возрастает ли он. Ожидаемо, сложность возрастает на одну степень, решение не проходит все тесты.
Как сделать оптимальнее?
Ответы (1 шт):
счетчик = 0
Проверять, что каждый последующий элемент строго больше предыдущего. Если условие не выполняется, то счетчик += 1 и проверить, что текущий элемент так же больше пред-предыдущего. Если в конце счетчик 0 или 1, то задача выполнима. Если 2, то можно сразу все заканчивать, потому что задача невыполнима.