Una lista de números se llama monotónicamente creciente (o no decreciente) si cada elemento es mayor o igual al elemento anterior.

Por ejemplo, 1, 1, 2, 4, 5, 5, 5, 8, 10, 11, 14, 14está aumentando monotónicamente.

Dada una lista monótonamente creciente de enteros positivos que tiene un número arbitrario de puntos vacíos denotados por ?, complete los espacios vacíos con enteros positivos de modo que haya tantos enteros únicos como sea posible presentes en la lista, pero sigue siendo monotónicamente creciente.

Puede haber múltiples formas de lograr esto. Cualquiera es valido.

Salida de la lista resultante.

Por ejemplo , si la entrada es

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

se garantiza que sin los espacios vacíos la lista aumentará monotónicamente

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

y su tarea es asignar números enteros positivos a cada uno ?para maximizar el número de números enteros distintos en la lista mientras se mantiene sin disminución.

Una tarea que no es válida es

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

porque, aunque no es decreciente, solo tiene un número entero más que la entrada, a saber 3.

En este ejemplo, es posible insertar seis enteros positivos únicos y mantener la lista no decreciente.
Un par de formas posibles son:

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

Cualquiera de estos (y muchos otros) sería una salida válida.

Todos los espacios vacíos deben llenarse.

No hay límite superior en los enteros que se pueden insertar. Está bien si se imprimen enteros muy grandes en notación científica.

El cero no es un entero positivo y nunca debe insertarse.

En lugar de ?que puede utilizar cualquier valor constante que no es un entero positivo, como por ejemplo 0, -1, null, False, o "".

El código más corto en bytes gana.

Más ejemplos

[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

ftoma una lista y devuelve una lista, donde 0 representa ?s.

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

Básicamente, la primera lista de exploración desde la izquierda, reemplazando 0 por uno más que el elemento anterior (o 0 al inicio); luego escanee desde la derecha reduciendo elementos demasiado grandes para igualar el de su derecha.

Pruébalo en línea! (con envoltorio para convertir ?s.)

Mathematica, 84 bytes

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

Función pura que toma una lista como argumento, donde los espacios vacíos se denotan por Null(como en {1, Null, Null, 2, Null}) o se eliminan por completo (como en {1, , , 2, }), y devuelve una lista adecuada (en este caso {1, 2, 2, 2, 3}).

Resulta que estoy usando el mismo algoritmo que en la respuesta de Haskell de Ørjan Johansen : primero reemplace cada Nulluno por uno más que el número a su izquierda ( //.{a___,b_,,c___}:>{a,b,b+1,c}), luego reemplace cualquier número demasiado grande por el número a su derecha ( //.{a___,b_,c_,d___}/;b>c:>{a,c,c,d}). Para tratar con posibles Nulls al comienzo de la lista, comenzamos anteponiendo a 0( {0,##}&@@#), haciendo el algoritmo y luego eliminando el inicial 0( Rest).

Sí, elegí en Nulllugar de Xo algo así para guardar literalmente un byte en el código (el que de otro modo estaría entre comas b_,,c___).

C 160

Esto nunca ganará pero:

#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)}

Toma la lista de los argumentos de la línea de comando.

05AB1E , 31 23 13 bytes

Guardado 10 bytes gracias a Grimy

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

Pruébalo en línea!

Explicación

ε      ]       # 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

Toma datos como múltiples argumentos de línea de comandos separados por espacios. Emite la lista de resultados un número por línea. Pruébalo en línea! (He eludido la cuestión de los argumentos múltiples de la línea de comandos porque sería difícil agregar 25 argumentos en TIO, pero también funciona como se anuncia).

Explicación

Procedemos en dos pases. Primero, reemplazamos cada ejecución de ?s en la entrada con una secuencia que comienza desde el número anterior en la lista y aumenta en uno 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

Luego volvemos a recorrerlo; para cada número, imprimimos el mínimo y todos los números a su derecha. Esto reduce los números demasiado altos para mantener la monotonicidad.

                      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 con NumPy, 163 bytes

Guardado 8 bytes gracias a @wythagoras

Los ceros solían marcar espacios vacíos

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:]

Más legible con comentarios:

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)," ";

toma datos de los argumentos de la línea de comandos, imprime una lista separada por espacios. Corre con -nr.

Descompostura

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

$nes verdadero para cualquier cadena que no sea la cadena vacía y "0".
$n>0es verdadero para números positivos y cadenas que los contienen.

Perl 6 , 97 bytes

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

La entrada es una lista de valores o una cadena separada por espacios, donde ?se usa para reemplazar los valores que se reemplazarán.

La salida es una cadena separada por espacios con un espacio final.

Intentalo

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 quería usarlo reduceRight. Explicación: El mapreemplaza cada valor falso por uno más que el valor anterior, luego el reduceRighttrabajo retrocede desde el final asegurando que ningún valor exceda el siguiente valor.

Q, 63 bytes

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

Esencialmente el mismo algoritmo que la respuesta de Haskell de Ørjan Johansen .

• Asume? = 0.
• Inserta un 0 al comienzo de la matriz en caso de? al principio.
• Escanea la matriz reemplazando 0 con 1 + elemento anterior.
• Invierte la matriz y escanea nuevamente, reemplazando elementos mayores que el elemento anterior con el elemento anterior.
• Invierte y corta el primer elemento (el 0 agregado desde el principio).

El uso de min vs last se usó para guardar un byte, ya que se puede suponer que el último elemento será el elemento min dado el tipo descendente de la 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

Un puerto simple de la respuesta de Haskell de Ørjan Johansen a TI-Basic. Utiliza 0 como valor nulo. Toma información de L ₁ .

Explicación:

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 la matriz de entrada en lugar de devolver una nueva para guardar bytes.
Usos en 0lugar de ?.

Pruébalo en línea.

Explicación:

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

Pruébalo en línea!

Usos en 0lugar de?

JavaScript (ES6), 59

Una función con una matriz entera como entrada. Los espacios vacíos están marcados con0

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

Prueba

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 la misma estrategia que Ørjan Johansen.

Utiliza 0 en la lista de entrada para marcar la var.

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+" ");};

Pruébalo en línea!

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

Pruébalo en línea!