Pular para o conteudo principal
SeniorPath
Explorar conteudo
Menu / Fechar menu

24 de Março

Pilha com mínimo

Como manter o mínimo atualizado em O(1) com uma estrutura auxiliar simples.

Pilha Intermediario 15 min TypeScript

#interviews#stack#design

Implemente uma pilha que suporte:

  • push(x)
  • pop()
  • top()
  • getMin()

Todas as operações devem rodar em O(1).

Na versão original, isso costuma vir como uma classe. Aqui no SeniorPath, use:

  • operations: lista de operações
  • values: valor associado a cada operação, ou null quando não houver

E retorne um array com as respostas de cada operação. Operações que não retornam valor devem devolver null.

Exemplo:

Input:
  operations = ["MinStack","push","push","push","getMin","pop","top","getMin"]
  values     = [null,-2,0,-3,null,null,null,null]

Output:
  [null,null,null,null,-3,null,0,-2]

O que perceber antes de codar

  • O desafio não e empilhar e desempilhar. E manter o mínimo sempre pronto.
  • O mínimo muda junto com `push` e `pop`.
  • O segredo e manter uma invariante auxiliar sincronizada.

Erros comuns

  • percorrer a pilha inteira em cada `getMin`
  • esquecer de atualizar a estrutura auxiliar no `pop`

Passo 1 - Entender o que realmente esta difícil

Pilha normal já e fácil:

  • push
  • pop
  • top

O ponto do problema e outro:

  • como responder getMin() em O(1)?

Passo 2 - Escrever a versão inicial mais direta

A versão inicial natural e:

  • manter uma pilha normal
  • quando vier getMin, procurar o menor nela inteira

Funciona.

Mas getMin vira O(n).

Passo 3 - Perguntar que informação precisa ficar sempre pronta

Em cada posição da pilha, o que importa não e só o valor atual.

Também importa:

  • qual era o menor valor até aqui?

Passo 4 - Transformar isso em invariante

A forma simples e manter uma segunda pilha:

  • stack guarda os valores
  • mins guarda o menor valor correspondente a cada profundidade

Assim, o topo de mins e sempre a resposta de getMin.

O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.

Codigo inicial

export function runMinStack(operations, values) {
  // operations example: ["MinStack", "push", "getMin"]
  // values example: [null, 3, null]
  // sua solução aqui
  return []
}
solution.ts
Travado? Dicas disponiveis.

Ainda não resolveu?

Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.

Abrir a solucao de referencia

Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.

Solução

Complexidade final

Tempo: O(1)

Espaço: O(n)

Solução 1 - Pilha simples mais varredura no getMin

Boa versão inicial para deixar claro onde esta o gargalo.

export function runMinStack(operations, values) {
  const stack = []
  const output = []

  for (let index = 0; index < operations.length; index += 1) {
    const operation = operations[index]
    const value = values[index]

    if (operation === "MinStack") {
      output.push(null)
    } else if (operation === "push") {
      stack.push(value)
      output.push(null)
    } else if (operation === "pop") {
      stack.pop()
      output.push(null)
    } else if (operation === "top") {
      output.push(stack[stack.length - 1] ?? null)
    } else if (operation === "getMin") {
      output.push(Math.min(...stack))
    }
  }

  return output
}

Funciona, mas getMin custa caro demais porque vira O(n).

Solução 2 - Pilha auxiliar de minimos

Agora a informação derivada fica sempre atualizada.

export function runMinStack(operations, values) {
  const stack = []
  const mins = []
  const output = []

  for (let index = 0; index < operations.length; index += 1) {
    const operation = operations[index]
    const value = values[index]

    if (operation === "MinStack") {
      output.push(null)
    } else if (operation === "push") {
      stack.push(value)

      const currentMin = mins.length === 0 ? value : Math.min(value, mins[mins.length - 1])
      mins.push(currentMin)
      output.push(null)
    } else if (operation === "pop") {
      stack.pop()
      mins.pop()
      output.push(null)
    } else if (operation === "top") {
      output.push(stack[stack.length - 1] ?? null)
    } else if (operation === "getMin") {
      output.push(mins[mins.length - 1] ?? null)
    }
  }

  return output
}

O ponto central e a invariante: mins[i] sempre representa o menor valor dos primeiros i + 1 elementos.

O que dizer na entrevista

Uma explicação curta e boa seria:

A pilha normal resolve push, pop e top, mas não getMin em O(1) se eu precisar varrer tudo. Entao eu mantenho uma segunda pilha sincronizada com os minimos. Cada posição guarda o menor valor até aquele ponto. Assim getMin vira só olhar o topo dessa pilha auxiliar.

Isso mostra que você:

  • identificou exatamente qual operação quebra a complexidade
  • respondeu com uma invariante simples
  • explicou a modelagem sem teatralidade

Quando esse padrão aparece de novo

Esse padrão reaparece quando você precisa:

  • manter informação derivada sempre pronta
  • projetar estrutura com restrição de complexidade
  • sincronizar estado principal com estado auxiliar
  • pensar em invariantes por operação

O ponto não e decorar essa estrutura.

O ponto e aprender a manter a resposta pronta enquanto a estrutura muda.
Proximo desafio Implementar fila usando pilhas Desafio anterior Os k elementos mais frequentes

Desafios relacionados

Parênteses válidos

Maior substring sem caracteres repetidos

Três somas

Artigos relacionados

Enquadrar o problema antes de codificar

Como Explicar sua Solução sem se Perder

Reconhecer padrões em problemas