Uma lista de números é chamada de aumento monotônico (ou não decrescente), pois todo elemento é maior ou igual ao elemento anterior.

Por exemplo, 1, 1, 2, 4, 5, 5, 5, 8, 10, 11, 14, 14está aumentando monotonicamente.

Dada uma lista monotonicamente crescente de números inteiros positivos que possui um número arbitrário de pontos vazios indicado por ?, preencha os pontos vazios com números inteiros positivos, de modo que o maior número possível de números únicos possíveis esteja presente na lista, mas ele continua aumentando monotonicamente.

Pode haver várias maneiras de conseguir isso. Qualquer um é válido.

Saída da lista resultante.

Por exemplo , se a entrada for

?, 1, ?, 1, 2, ?, 4, 5, 5, 5, ?, ?, ?, ?, 8, 10, 11, ?, 14, 14, ?, ?

é garantido que, sem os espaços vazios, a lista aumentará monotonicamente

1, 1, 2, 4, 5, 5, 5, 8, 10, 11, 14, 14

e sua tarefa é atribuir números inteiros positivos a cada um ?para maximizar o número de números inteiros distintos na lista, mantendo-os não decrescentes.

Uma tarefa que não é válida é

1, 1, 1, 1, 2, 3, 4, 5, 5, 5, 5, 5, 5, 5, 8, 10, 11, 14, 14, 14, 14, 14

porque, embora não diminua, ele possui apenas mais um número inteiro exclusivo que a entrada, a saber 3.

Neste exemplo, é possível inserir seis números inteiros positivos exclusivos e manter a lista não decrescente.
Algumas maneiras possíveis são:

1, 1, 1, 1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 8, 8, 10, 11, 12, 14, 14, 15, 16

1, 1, 1, 1, 2, 3, 4, 5, 5, 5, 5, 6, 6, 7, 8, 10, 11, 13, 14, 14, 20, 200

Qualquer um desses (e muitos outros) seria uma saída válida.

Todos os lugares vazios devem ser preenchidos.

Não há limite superior para números inteiros que podem ser inseridos. Tudo bem se números inteiros muito grandes forem impressos em notação científica.

Zero não é um número inteiro positivo e nunca deve ser inserido.

No lugar de ?que você pode usar qualquer valor consistente, que não é um número inteiro positivo, como 0, -1, null, False, ou "".

O código mais curto em bytes vence.

Mais exemplos

[input]
[one possible output] (a "*" means it is the only possible output)

2, 4, 10
2, 4, 10 *

1, ?, 3
1, 2, 3 *

1, ?, 4
1, 2, 4

{empty list}
{empty list} *

8
8 *

?
42

?, ?, ?
271, 828, 1729

?, 1
1, 1 *

?, 2
1, 2 *

?, 3
1, 3

45, ?
45, 314159265359

1, ?, ?, ?, 1
1, 1, 1, 1, 1 *

3, ?, ?, ?, ?, 30
3, 7, 10, 23, 29, 30 

1, ?, 2, ?, 3, ?, 4
1, 1, 2, 3, 3, 3, 4

1, ?, 3, ?, 5, ?, 7
1, 2, 3, 4, 5, 6, 7 *

1, ?, 3, ?, 5, ?, ?, 7
1, 2, 3, 4, 5, 6, 7, 7

1, ?, ?, ?, ?, 2, ?, ?, ?, ?, 4, ?, 4, ?, ?, 6
1, 1, 1, 1, 1, 2, 3, 4, 4, 4, 4, 4, 4, 5, 6, 6

98, ?, ?, ?, 102, ?, 104
98, 99, 100, 101, 102, 103, 104 *

Haskell , 41 bytes

fpega uma lista e retorna uma lista, com 0 representando ?s.

f=scanr1 min.tail.scanl(#)0
m#0=m+1
_#n=n

Basicamente, a primeira lista de varredura da esquerda, substituindo 0s por um a mais que o elemento anterior (ou 0 no início); em seguida, digitalize da direita, reduzindo elementos muito grandes para igualar à direita.

Experimente online! (com invólucro para converter ?s.)

Mathematica, 84 bytes

Rest[{0,##}&@@#//.{a___,b_,,c___}:>{a,b,b+1,c}//.{a___,b_,c_,d___}/;b>c:>{a,c,c,d}]&

Função pura, tendo uma lista como argumento, onde os pontos vazios são denotados por Null(como em {1, Null, Null, 2, Null}) ou excluídos por completo (como em {1, , , 2, }) e retornando uma lista adequada (neste caso {1, 2, 2, 2, 3}).

Acontece que estou usando o mesmo algoritmo da resposta Haskell de Ørjan Johansen : primeiro substitua cada Nullum por um a mais que o número à esquerda ( //.{a___,b_,,c___}:>{a,b,b+1,c}), depois substitua qualquer número muito grande pelo número à direita ( //.{a___,b_,c_,d___}/;b>c:>{a,c,c,d}). Para lidar com possíveis Nulls no início da lista, começamos adicionando a 0( {0,##}&@@#), executando o algoritmo e excluindo a inicial 0( Rest).

Sim, eu escolhi em Nullvez de Xou algo assim para salvar literalmente um byte no código (aquele que seria entre as vírgulas de b_,,c___).

C 160

Isso nunca vai ganhar, mas:

#define p(x)printf("%d ",x);
i=1,l=0,m=0,n;main(c,v)char**v;{for(;i<c;i++)if(*v[i]==63)m++;else{for(n=atoi(v[i]);m>0;m--)p(l<n?++l:n)p(l=n)}for(;m>0;m--)p(++l)}

Ele pega a lista nos argumentos da linha de comando.

05AB1E , 31 23 13 bytes

Economizou 10 bytes graças ao Grimy

ε®X:D>U].sR€ß

Experimente online!

Explicação

ε      ]       # apply to each number in input
 ®X:           # replace -1 with X (initially 1)
    D>U        # store current_number+1 in X
        .s     # get a list of suffixes
          R    # reverse
           ۧ  # take the minimum of each

Pip , 25 23 21 bytes

Y{Y+a|y+1}MgW PMNyPOy

Recebe entrada como vários argumentos de linha de comando separados por espaço. Emite a lista de resultados um número por linha. Experimente online! (Eu falsifiquei a coisa de vários argumentos da linha de comando, porque seria difícil adicionar 25 argumentos no TIO, mas funciona como anunciado também.)

Explicação

Prosseguimos em dois passes. Primeiro, substituímos todas as execuções de ?s na entrada por uma sequência iniciando no número anterior da lista e aumentando em um a cada vez:

? 1 ? 1 2 ? 4 5 5 5 ? ? ? ? 8 10 11 ?  14 14 ?  ?
1 1 2 1 2 3 4 5 5 5 6 7 8 9 8 10 11 12 14 14 15 16

Então passamos novamente; para cada número, imprimimos o mínimo e todos os números à direita. Isso reduz os números altos demais para manter a monotonicidade.

                      y is initially "", which is 0 in numeric contexts
                      Stage 1:
 {       }Mg           Map this function to list of cmdline args g:
   +a                  Convert item to number: 0 (falsey) if ?, else nonzero (truthy)
     |                 Logical OR
      y+1              Previous number +1
  Y                    Yank that value into y (it is also returned for the map operation)
Y                      After the map operation, yank the whole result list into y
                      Stage 2:
            W          While loop, with the condition:
               MNy      min(y)
              P         printed (when y is empty, MN returns nil, which produces no output)
                  POy  Inside the loop, pop the leftmost item from y

Python 2 com NumPy, 163 bytes

Guardado 8 bytes graças a @wythagoras

Zeros usados ​​para marcar pontos vazios

import numpy
l=[1]+input()
z=numpy.nonzero(l)[0]
def f(a,b):
 while b-a-1:a+=1;l[a]=l[a-1]+1;l[a]=min(l[a],l[b])
i=1
while len(z)-i:f(z[i-1],z[i]);i+=1
print l[1:]

Mais legível com comentários:

import numpy
l=[1]+input()           # add 1 to the begining of list to handle leading zeros
z=numpy.nonzero(l)[0]   # get indices of all non-zero values
def f(a,b):             # function to fill gap, between indices a and b
    while b-a-1:
        a+=1
        l[a]=l[a-1]+1   # set each element value 1 larger than previous element
        l[a]=min(l[a],l[b])   # caps it by value at index b
i=1
while len(z)-i:       
    f(z[i-1],z[i])      # call function for every gap
    i+=1
print l[1:]             # print result, excluding first element, added at the begining

PHP, 95 77 71 69 68 bytes

for($p=1;$n=$argv[++$i];)echo$p=$n>0?$n:++$p-in_array($p,$argv)," ";

recebe entrada de argumentos da linha de comando, imprime lista separada por espaço. Corra com -nr.

demolir

for($p=1;$n=$argv[++$i];)   # loop through arguments
    echo$p=                     # print and copy to $p:
    $n>0                            # if positive number
        ?$n                             # then argument
        :++$p                           # else $p+1 ...
            -in_array($p,$argv)         # ... -1 if $p+1 is in input values
    ," ";                       # print space

$né verdadeiro para qualquer string, exceto a string vazia e "0".
$n>0é verdade para números positivos - e cadeias que os contêm.

Perl 6 , 97 bytes

{my $p;~S:g/(\d+' ')?<(('?')+%%' ')>(\d*)/{flat(+($0||$p)^..(+$2||*),(+$2 xx*,($p=$2)))[^+@1]} /}

A entrada é uma lista de valores ou uma sequência separada por espaço, onde ?é usada para substituir os valores a serem substituídos.

Saída é uma cadeia separada por espaço com um espaço à direita.

Tente

Expandido:

{                       # bare block lambda with implicit parameter ｢$_｣

    my $p;              # holds the previous value of ｢$2｣ in cases where
                        # a number is sandwiched between two replacements

    ~                   # stringify (may not be necessary)
    S                   # replace
    :global
    /
        ( \d+ ' ' )?    # a number followed by a space optionally ($0)

        <(              # start of replacement

          ( '?' )+      # a list of question marks
          %%            # separated by (with optional trailing)
          ' '           # a space

        )>              # end of replacement

        (\d*)           # an optional number ($2)

    /{                  # replace with the result of:

        flat(

          +( $0 || $p ) # previous value or 0
          ^..           # a range that excludes the first value
          ( +$2 || * ), # the next value, or a Whatever star

          (
            +$2 xx *,   # the next value repeated endlessly

            ( $p = $2 ) # store the next value in ｢$p｣
          )

        )[ ^ +@1 ]      # get as many values as there are replacement chars
    } /                 # add a space afterwards
}

JavaScript (ES6), 65 bytes

a=>a.map(e=>a=e||-~a).reduceRight((r,l)=>[r[0]<l?r[0]:l,...r],[])

Porque eu queria usar reduceRight. Explicação: O mapsubstitui cada valor falso por um a mais que o valor anterior e, em seguida, reduceRighttrabalha de volta a partir do final, garantindo que nenhum valor exceda o valor a seguir.

Q, 63 bytes

{1_(|){if[y>min x;y-:1];x,y}/[(|){if[y=0;y:1+-1#x];x,y}/[0,x]]}

Essencialmente, o mesmo algoritmo da resposta Haskell de Ørjan Johansen .

• Assume? = 0.
• Insere um 0 no início da matriz em caso de? no início.
• Verifica a matriz substituindo 0 por 1 + elemento anterior.
• Inverte a matriz e varre novamente, substituindo elementos maiores que o elemento anterior pelo elemento anterior.
• Inverte e corta o primeiro elemento (o 0 adicionado desde o início).

O uso de min vs last foi usado para salvar um byte, pois pode assumir que o último elemento será o elemento min, de acordo com o tipo decrescente da matriz.

TI-Basic (TI-84 Plus CE), 81 bytes

not(L1(1))+L1(1→L1(1
For(X,2,dim(L1
If not(L1(X
1+L1(X-1→L1(X
End
For(X,dim(L1)-1,1,-1
If L1(X)>L1(X+1
L1(X+1→L1(X
End
L1

Um simples porto de Haskell de Ørjan Johansen responde à TI-Basic. Usa 0 como valor nulo. Recebe entrada de L ₁ .

Explicação:

not(L1(1))+L1(1→L1(1 # if it starts with 0, change it to a 1
For(X,2,dim(L1     # starting at element 2:
If not(L1(X              # if the element is zero
1+L1(X-1→L1(X            # change the element to one plus the previous element
End
For(X,dim(L1)-1,1,-1 # starting at the second-last element and working backwards
If L1(X)>L1(X+1           # if the element is greater than the next
L1(X+1→L1(X               # set it equal to the next
End
L1                   # implicitly return

Java 8, 199 164 bytes

a->{for(int l=a.length,n,j,x,i=0;i<l;)if(a[i++]<1){for(n=j=i;j<l;j++)if(a[j]>0){n=j;j=l;}for(j=i-3;++j<n-1;)if(j<l)a[j+1]=j<0?1:a[j]+(l==n||a[n]>a[j]|a[n]<1?1:0);}}

Modifica a matriz de entrada em vez de retornar uma nova para salvar bytes.
Usa em 0vez de ?.

Experimente online.

Explicação:

a->{                      // Method with integer-array parameter and no return-type
  for(int l=a.length,     //  Length of the input-array
      n,j,x,              //  Temp integers
      i=0;i<l;)           //  Loop `i` over the input-array, in the range [0, length):
    if(a[i++]<1){         //   If the `i`'th number of the array is 0:
                          //   (And increase `i` to the next cell with `i++`)
      for(n=j=i;          //    Set both `n` and `j` to (the new) `i`
          j<l;j++)        //    Loop `j` in the range [`i`, length):
        if(a[j]>0){       //     If the `j`'th number of the array is not 0:
          n=j;            //      Set `n` to `j`
          j=l;}           //      And set `j` to the length to stop the loop
                          //    (`n` is now set to the index of the first non-0 number 
                          //     after the `i-1`'th number 0)
      for(j=i-3;++j<n-1;) //    Loop `j` in the range (`i`-3, `n-1`):
        if(j<l)           //     If `j` is still within bounds (smaller than the length)
          a[j+1]=         //      Set the `j+1`'th position to:
            j<0?          //       If `j` is a 'position' before the first number
             1            //        Set the first cell of the array to 1
            :             //       Else:
             a[j]+        //        Set it to the `j`'th number, plus:
              (l==n       //        If `n` is out of bounds bounds (length or larger)
               ||a[n]>a[j]//        Or the `n`'th number is larger than the `j`'th number
               |a[n]<1?   //        Or the `n`'th number is a 0
                1         //         Add 1
               :          //        Else:
                0);}}     //         Leave it unchanged by adding 0

Python 2 , 144 124 119 bytes

l=input()
for n in range(len(l)):a=max(l[:n]+[0]);b=filter(abs,l[n:]);b=len(b)and b[0]or-~a;l[n]=l[n]or a+(b>a)
print l

Experimente online!

Usa em 0vez de?

JavaScript (ES6), 59

Uma função com uma matriz inteira como entrada. Os pontos vazios são marcados com0

a=>a.map((v,i)=>v?w=v:(a.slice(i).find(x=>x)<=w?w:++w),w=0)

Teste

var F=
a=>a.map((v,i)=>v?w=v:(a.slice(i).find(x=>x)<=w?w:++w),w=0)

;[[2, 4, 10]
,[1, 0, 3]
,[1, 0, 4]
,[]
,[8]
,[0]
,[0, 0, 0]
,[0, 1]
,[0, 2]
,[0, 3]
,[45, 0]
,[1, 0, 0, 0, 1]
,[3, 0, 0, 0, 0, 30]
,[1, 0, 2, 0, 3, 0, 4]
,[1, 0, 3, 0, 5, 0, 7]
,[1, 0, 3, 0, 5, 0, 0, 7]
,[1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 4, 0, 4, 0, 0, 6]
,[98, 0, 0, 0, 102, 0, 104]]
.forEach(a=>{
  console.log(a+'\n'+F(a))
})

C # (.NET Core) , 182 bytes

Usando a mesma estratégia que Ørjan Johansen.

Usa 0 na lista de entrada para marcar a var desconhecida.

l=>{if(l[0]<1)l[0]=1;int j;for(j=0;j<l.Length;j++)l[j]=l[j]==0?l[j-1]+1:l[j];for(j=l.Length-2;j>=0;j--)l[j]=l[j]>l[j+1]?l[j+1]:l[j];foreach(var m in l) System.Console.Write(m+" ");};

Experimente online!

Perl 5 -p , 99 bytes

s,(\d+ )?\K((\? )+)(?=(\d+)),$d=$1;$l=$4;$2=~s/\?/$d<$l?++$d:$l/rge,ge;($d)=/.*( \d+)/;s/\?/++$d/ge

Experimente online!