Peter Wu's questions

Estou trabalhando em um problema de otimização para encontrar uma região que maximize uma certa função objetivo, estou usando um conjunto de coordenadas de pixel para manter o controle da região, e para cada passo adicionarei ou removerei um pixel no limite para ver se a função objetivo aumenta ou não. Espero que a região seja conectada, há alguma estrutura de dados que possa decidir rapidamente se remover um pixel tornaria a região desconectada? Aqui, assumimos que um pixel está conectado a seus quatro vizinhos.

E uma pergunta paralela: e se eu esperar que a região seja sempre simplesmente conectada? Por simplesmente conectada, quero dizer que não há buraco, e adicionar um pixel pode criar um buraco.

O problema é baseado em um problema de concurso leetcode ( https://doocs.github.io/leetcode/en/lc/3281/ ). Pode-se reduzi-lo ao seguinte problema: seja s um array ordenado e d um inteiro positivo, minimize ( s [i]- s [j]+ d )/(ij). Em que i>j.

A maioria das respostas foi baseada em busca binária para limitar uma solução ótima, para a qual a complexidade de tempo é dependente de max( s )-min( s ). Então é possível construir um algoritmo que seja linear/subquadrático em relação ao tamanho de s ?