Remove K Digits

Q: Какова временная сложность алгоритма Remove K Digits?

С монотонным стеком алгоритм работает за время O(n) для n цифр: каждая цифра добавляется в стек один раз, а каждое извлечение расходует одно из k удалений. В стеке хранится до n цифр, поэтому дополнительная память составляет O(n) . Повторное сканирование слева для каждого удаления занимает O(n·k) .

СреднеМонотонный стек Жадные алгоритмы

+10

Дано неотрицательное число, записанное в виде строки цифр num, и целое число k. Удали ровно k цифр и сохрани остальные в исходном порядке так, чтобы оставшееся число было как можно меньше.

Верни его в виде строки без ведущих нулей. Если ничего не осталось или остались только нули, верни "0".

Функция

removeKdigits(num: string, k: integer) → string

numstring: число, записанное в виде строки цифр
kinteger: сколько цифр удалить
Возвращаетstring: наименьшее число, которое можно оставить в виде строки без ведущих нулей

Ограничения

1 ≤ num.length ≤ 4 × 10⁴
0 ≤ k ≤ num.length
num содержит только цифры от 0 до 9.
num не содержит ведущих нулей, кроме случая, когда само число равно нулю: "0".

Примеры

Ввод: num = "4325043"k = 3
Вывод: "2043"
Пояснение: Удаление 4 и первой 3 ставит 2 впереди. 0 не может быть первым: перед ним стоят четыре цифры, а у тебя есть три удаления. При последнем удалении убирается 5, которая стоит перед меньшим 0.

Ввод: num = "30200"k = 1
Вывод: "200"
Пояснение: Если убрать 3, останется 0200, а без начального нуля это будет 200. При любом другом удалении 3 останется впереди, и получится четырёхзначное число, например 3000.

Ввод: num = "52"k = 2
Вывод: "0"
Пояснение: Обе цифры удаляются, поэтому ничего не остаётся, и ответ — "0".

Дополнительный вопрос

Как бы ты изменил решение, чтобы удалить k цифр и оставить наибольшее число?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Самые левые цифры имеют наибольший вес, поэтому нужно удалить первую цифру, которая больше своего правого соседа. Стек из цифр, которые вы сохраняете, позволяет применить это правило ко всей строке за один проход. Если к концу прохода останутся удаления, выполните их с конца, а ведущие нули удалите в последнюю очередь.

Удаляйте по одной цифре за раз

Верно, но не успевает на самых больших тестах

Идея

Удаляйте по одной цифре за раз: найдите первую позицию i, для которой num[i] > num[i+1], и удалите num[i]; если цифры никогда не убывают, удалите последнюю цифру. Повторите k раз.

В каждом ответе остаётся n-k цифр, поэтому ответ с меньшей цифрой в первой отличающейся позиции меньше. До позиции i цифры никогда не убывают, поэтому удаление более ранней цифры сдвигает на её место цифру не меньше; удаление более поздней оставляет большую num[i] на месте. Удаление num[i] уменьшает цифру в самой ранней позиции, которую можно уменьшить.

После каждого удаления выполняется повторный просмотр слева и сдвигаются следующие за удалённой цифры, поэтому объём работы составляет O(n·k). Для 40,000 единиц при k = 25,000 во время просмотров считывается около 6.9 × 10^8 цифр.

Алгоритм

Скопируйте цифры в список, из которого можно удалять элементы.
Повторите k раз: двигайтесь слева направо до первой цифры, которая больше следующей, или до последней цифры, и удалите её.
Удалите ведущие нули и верните "0", если ничего не осталось.

def removeKdigits(num, k):
    digits = list(num)
    for _ in range(k):
        # Find the first digit that is bigger than the digit after it.
        # If the digits never go down, i stops on the last digit.
        i = 0
        while i + 1 < len(digits) and digits[i] <= digits[i + 1]:
            i += 1
        del digits[i]
    result = "".join(digits).lstrip("0")
    return result if result else "0"

Монотонный стек сохранённых цифр

Идея

После того как медленная версия удаляет num[i], цифры перед i по-прежнему никогда не уменьшаются, поэтому следующее удаление может начаться только с цифры перед пробелом. Стек хранит этот префикс: оставленные цифры, которые никогда не убывают снизу вверх. Когда новая цифра меньше верхней, верхняя больше своей правой соседней цифры — той, которую удалила бы медленная версия. Удали её, потрать одно удаление и продолжай удалять, пока новая верхняя цифра всё ещё больше.

Для 4325043 при k = 3 цифра 3 удаляет 4, цифра 2 удаляет 3, а цифра 0 удаляет 5. Цифры 4 и 3 добавляются в стек по мере поступления, в результате получается 2043.

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

Алгоритм

Создайте пустой стек цифр.
Для каждой цифры числа num: пока остались удаления и верхний элемент стека больше этой цифры, извлеките верхний элемент и выполните одно удаление. Затем добавьте цифру в стек.
Если после цикла остались удаления, удалите такое же количество цифр с вершины стека.
Прочитайте стек снизу вверх, пропустите ведущие нули и верните оставшуюся часть или "0", если ничего не осталось.

def removeKdigits(num, k):
    stack = []  # kept digits, never decreasing from bottom to top
    for digit in num:
        # A bigger digit right before a smaller one: dropping it makes the number smaller.
        while k > 0 and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    # The kept digits never decrease, so any removals left come off the end.
    stack = stack[:len(stack) - k]
    result = "".join(stack).lstrip("0")
    return result if result else "0"

Ловушки и крайние случаи

Удаление элемента, когда верхний элемент равен новой цифре. В 112 при k = 1 останется 12; правильный ответ — 11.
Забыть удалить оставшиеся после цикла элементы или удалять их с начала. Стек не уменьшается, поэтому его последние цифры идут подряд: для 123456789 при k = 3 результат — 123456.
Считать удалённые нули удалениями. В 100200 при k = 1 удаляется только цифра 1; нули в начале удаляются бесплатно, и ответ — 200.
Вернуть пустую строку. В 10 при k = 1 остаётся только ноль, поэтому ответ — "0".
Преобразовать num в целое число. В нём может быть 4 × 10^4 цифр — намного больше, чем поддерживает любой целочисленный тип, поэтому сравнивайте цифры как символы.

Частые вопросы3

Какова временная сложность алгоритма Remove K Digits?

С монотонным стеком алгоритм работает за время O(n) для n цифр: каждая цифра добавляется в стек один раз, а каждое извлечение расходует одно из k удалений. В стеке хранится до n цифр, поэтому дополнительная память составляет O(n). Повторное сканирование слева для каждого удаления занимает O(n·k).

Как обрабатывать ведущие нули в задаче Remove K Digits?

Сначала удалите цифры, а нули убирайте только в конце. Ноль в начале не меняет значение, поэтому его удаление ничего не стоит: 10200 при k = 1 превращается в 0200, а затем в 200. Если после удаления ничего не осталось, верните "0".

Можно ли решить задачу «Удалить K цифр» с дополнительной памятью O(1)?

Да, если можно изменить входные данные. В стеке никогда не хранится больше цифр, чем вы уже прочитали, поэтому его можно разместить в начале самого массива цифр, используя один индекс для его вершины. В языках с неизменяемыми строками всё равно нужна одна копия цифр, что составляет O(n).

def removeKdigits(num, k):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

num = "4325043"
k = 3

Ожидаемый вывод

"2043"