Remove K Digits

Q: Qual é a complexidade de tempo de Remove K Digits?

Com uma pilha monotônica, ele é executado em tempo O(n) para n dígitos: cada dígito é empilhado uma vez, e cada remoção desempilha um dos k elementos a serem removidos. A pilha comporta até n dígitos, então o espaço extra é O(n) . Percorrer novamente da esquerda para a direita a cada remoção custa O(n·k) .

MédioPilha monotônica Guloso

+10

Você recebe um número não negativo escrito como uma string de dígitos, num, e um inteiro k. Remova exatamente k dígitos e mantenha os demais na ordem original, de modo que o número restante seja o menor possível.

Retorne-o como uma string sem zeros à esquerda. Se nada restar ou restarem apenas zeros, retorne "0".

Função

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

numstring: o número, escrito como uma sequência de dígitos
kinteger: quantos dígitos remover
Retornastring: o menor número que você pode deixar, como uma string sem zeros à esquerda

Restrições

1 ≤ num.length ≤ 4 × 10⁴
0 ≤ k ≤ num.length
num contém apenas os dígitos 0 a 9.
num não tem zeros à esquerda, exceto quando ele próprio é o número zero, "0".

Exemplos

Entrada: num = "4325043"k = 3
Saída: "2043"
Explicação: Descartar o 4 e o primeiro 3 coloca o 2 na frente. O 0 não pode ficar na frente: há quatro dígitos antes dele e você tem três remoções. A última remoção pega o 5, que fica antes de um 0 menor.

Entrada: num = "30200"k = 1
Saída: "200"
Explicação: Ao remover o 3, restam 0200 e, sem o zero à esquerda, isso é 200. Qualquer outra remoção mantém o 3 na frente e resulta em um número de quatro dígitos, como 3000.

Entrada: num = "52"k = 2
Saída: "0"
Explicação: Ambos os dígitos são removidos, então nada resta e a resposta é "0".

Para ir além

Como você alteraria a solução para remover k dígitos e deixar o maior número?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Os dígitos mais à esquerda têm maior peso, então o primeiro dígito que for maior que o vizinho à direita deve ser removido. Uma pilha com os dígitos que você mantém aplica essa regra à string inteira em uma única passagem. As remoções que sobrarem no final são feitas por trás, e os zeros à esquerda são removidos por último.

Remova um dígito de cada vez

Correta, mas não termina nos maiores testes

Intuição

Remova um dígito por vez: encontre a primeira posição i em que num[i] > num[i+1] e exclua num[i], ou exclua o último dígito se os dígitos nunca diminuírem. Repita k vezes.

Toda resposta mantém n-k dígitos, então a primeira posição em que duas respostas diferem determina qual é menor. Até i, os dígitos nunca diminuem, então excluir um dígito anterior desloca para essa posição um dígito pelo menos tão grande; excluir um posterior mantém o grande num[i] no lugar. Excluir num[i] reduz o valor na primeira posição que pode ser reduzida.

Cada remoção faz uma nova varredura a partir da esquerda e desloca os dígitos seguintes, então o trabalho é O(n·k). Em 40,000 uns com k = 25,000, as varreduras leem cerca de 6.9 × 10^8 dígitos.

Algoritmo

Copie os dígitos para uma lista da qual você possa excluir elementos.
Repita k vezes: percorra da esquerda para a direita até encontrar o primeiro dígito maior que o próximo ou chegar ao último dígito, e exclua-o.
Remova os zeros à esquerda e retorne "0" se não restar nada.

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"

Pilha monotônica de dígitos mantidos

Intuição

Depois que a versão lenta exclui num[i], os dígitos antes de i ainda nunca diminuem, então a próxima remoção só pode começar no dígito antes da lacuna. Uma pilha armazena esse prefixo: os dígitos mantidos, nunca decrescentes da base ao topo. Quando um novo dígito é menor que o do topo, o dígito do topo é maior que seu vizinho à direita, o dígito que a versão lenta excluiria. Remova-o, use uma remoção e continue removendo enquanto o novo dígito do topo ainda for maior.

Em 4325043 com k = 3, o 3 remove o 4, o 2 remove o 3 e o 0 remove o 5. O 4 e o 3 são inseridos à medida que aparecem, resultando em 2043.

Cada dígito é inserido uma vez e cada remoção usa uma das k remoções, então a passagem é O(n).

Algoritmo

Crie uma pilha vazia de dígitos.
Para cada dígito de num: enquanto ainda houver remoções e o topo da pilha for maior que o dígito, remova o topo e use uma remoção. Em seguida, empilhe o dígito.
Se ainda houver remoções após o loop, remova essa quantidade de dígitos do topo da pilha.
Leia a pilha de baixo para cima, ignore os zeros à esquerda e retorne o restante ou "0" se não sobrar nada.

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"

Armadilhas e casos extremos

Remover elementos quando o topo é igual ao novo dígito. Em 112 com k = 1, isso deixa 12; a resposta correta é 11.
Esquecer as remoções restantes após o loop ou fazê-las pelo início. A pilha nunca diminui, então seus últimos dígitos são: 123456789 com k = 3 resulta em 123456.
Contar os zeros removidos como remoções. Em 100200 com k = 1, o 1 é a única remoção; os zeros à frente saem de graça, e a resposta é 200.
Retornar uma string vazia. 10 com k = 1 deixa apenas um zero, então a resposta é "0".
Transformar num em um inteiro. Ele pode ter 4 × 10^4 dígitos, muito além do limite de qualquer tipo inteiro; portanto, compare os dígitos como caracteres.

Perguntas frequentes3

Qual é a complexidade de tempo de Remove K Digits?

Com uma pilha monotônica, ele é executado em tempo O(n) para n dígitos: cada dígito é empilhado uma vez, e cada remoção desempilha um dos k elementos a serem removidos. A pilha comporta até n dígitos, então o espaço extra é O(n). Percorrer novamente da esquerda para a direita a cada remoção custa O(n·k).

Como lidar com zeros à esquerda em Remove K Digits?

Remova os dígitos primeiro e remova os zeros somente no final. Um zero à esquerda não altera o valor, então não custa nenhuma remoção: 10200 com k = 1 se torna 0200 e depois 200. Se a remoção deixar o resultado vazio, retorne "0".

É possível resolver “Remover K Dígitos” com espaço extra O(1)?

Sim, se você puder alterar a entrada. A pilha nunca contém mais dígitos do que você já leu, então ela pode ficar no início do próprio array de dígitos, com um índice para o topo. Linguagens com strings imutáveis ainda precisam de uma cópia dos dígitos, o que é O(n).

def removeKdigits(num, k):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

num = "4325043"
k = 3

Saída Esperada

"2043"