Étant donné un tableau, puis-je trouver en O(n) la plus longue plage, dont les extrémités sont les plus grandes valeurs de la plage ?

Question

Pour un tableau d'entiers donné, trouvez la distance maximale entre 2 points (i et j) qui ont des valeurs plus élevées que tout élément entre eux.

Ejemplo:

values: 0 10  8  9  6  7  4 10  0
index : 0  1  2  3  4  5  6  7  8 

pour les valeurs ci-dessus la solution est i=1, j=7, mais

• si la valeur de l'indice 7 est 9 au lieu de 10 la solution est i=3, j=7
• si la valeur de l'indice 7 est 7 au lieu de 10 la solution est i=5, j=7

Je ne vois pas de solution en O(n) ... quelqu'un ?

Answer 1

Je pense que l'algorithme suivant s'exécute en O(n) temps et produit une solution optimale. C'est un peu délicat, donc je vais diviser la logique en deux cas, un dans lequel nous considérons le cas où il n'y a pas de valeurs dupliquées dans le tableau, et un dans lequel nous avons considéré le cas où les duplications sont autorisées.

La structure de données clé que nous utiliserons est le fichier Arbre cartésien Il s'agit d'un max-heap construit à partir d'une gamme de données et dont la propriété est qu'une marche en ordre des nœuds de l'arbre produit les valeurs de la séquence dans l'ordre dans lequel elles apparaissent. Le détail critique est qu'il est possible de construire un arbre cartésien pour une séquence d'éléments en O(n) temps.

À titre d'exemple, étant donné la séquence 4 1 0 3 2, nous obtiendrions cet arbre cartésien :

        4
         \
          3
         / \
        1   2
         \
          0

Remarquez que la marche en ordre donne effectivement 4 1 0 3 2.

Je prétends maintenant que les extrémités de l'intervalle que nous recherchons doivent être une paire parent/enfant dans l'arbre cartésien (c'est-à-dire que le premier nœud est un parent du second nœud ou vice-versa). Notez que nous sommes no en recherchant un nœud et n'importe quel ancêtre, mais spécifiquement une paire parent/enfant. Pour prouver cela, je prouve les deux affirmations suivantes :

Revendication 1 : Toute paire parent/enfant dans l'arbre cartésien définit une plage de valeurs dans la séquence originale qui n'a pas de valeurs intermédiaires supérieures aux points d'extrémité.

Revendication 2 : Toute plage de valeurs dans la séquence qui n'a pas de valeurs intermédiaires supérieures à ses points d'extrémité doit avoir ces points d'extrémité comme paire parent/enfant dans l'arbre cartésien.

Pris ensemble, ces éléments prouvent que l'intervalle que nous recherchons doit être une paire parent/enfant dans l'arbre cartésien. Cela nous donne alors un algorithme facile en temps linéaire pour résoudre le problème lorsque toutes les valeurs sont distinctes. Tout d'abord, en temps O(n), on construit un arbre cartésien pour l'intervalle. Ensuite, on explore récursivement l'arbre et, pour chaque paire parent/enfant, on trouve la distance entre ces paires, en prenant la plus grande plage trouvée. Cette deuxième étape s'exécute également en O(n), puisqu'un arbre cartésien est un arbre binaire et que le nombre d'arêtes est donc O(n).

Preuve de la première revendication : Une paire parent/enfant doit ressembler soit à

 u
  \
   v
  / \
 A   B

ou

    u
   /
  v
 / \
A   B

Rappelons qu'un arbre cartésien stocke ses éléments de manière à ce qu'une traversée en ordre des éléments de l'arbre donne les éléments du tableau utilisé pour produire l'arbre dans l'ordre dans lequel ils apparaissent dans le tableau. Cela signifie que dans le cas (1), nous regardons une plage d'éléments commençant par u, contenant tout A, et se terminant par b. De même, dans le cas (2), la plage commence par v, puis contient tout B, et se termine par u. Nous prouvons par contradiction l'affirmation selon laquelle u et v n'ont pas de valeurs intermédiaires plus grandes que u ou v. Supposons que ce soit le cas et que la valeur w soit plus grande que u ou v. Par la définition d'un arbre cartésien, si w est entre u et v dans la séquence originale, alors dans le cas (1) il doit être dans le sous-arbre A et dans le cas (2) il doit être dans le sous-arbre B. Mais un arbre cartésien est un max-heap, et donc dans le cas (1) à la fois u et v sont plus grands que tout dans A, et dans le cas (2) à la fois u et v sont plus grands que tout dans B, une contradiction. Ainsi, l'intervalle de valeurs entre toute paire parent/enfant ne doit pas être plus grand que le parent ou l'enfant.

Preuve de la revendication 2 : Par contrapositif ; nous montrons que s'il existe une sous-séquence du tableau original commençant par u et se terminant par v qui contient un élément plus grand w que u ou v, alors u et v ne peuvent pas être une paire parent/enfant ou enfant/parent dans l'arbre cartésien. La preuve est virtuellement identique à la précédente - si u et v étaient une paire parent/enfant, alors dans le cas (1) ci-dessus, w devrait être dans A et dans le cas (2), w devrait être dans B, dans les deux cas violant le fait qu'un arbre cartésien est un tas maximum.

Les preuves ci-dessus nous montrent que si toutes les valeurs sont distinctes, nous pouvons résoudre ce problème en temps linéaire en construisant simplement un arbre cartésien et en effectuant une simple marche dans l'arbre. Mais que se passe-t-il si les éléments peuvent être dupliqués, comme dans l'énoncé original du problème ? Dans ce cas, nous pouvons utiliser une structure d'arbre cartésien modifiée. Nous autoriserons les nœuds à être combinés en un "méta-nœud" de plusieurs valeurs différentes de l'arbre cartésien qui partagent la même valeur. Par exemple, la séquence 2 7 1 7 8 0 3 8 2 ressemblerait à ceci :

                  [8 ------- 8]
                  / \         \
                 /   3         2
                /   /
               /   0
              /
          [7 -- 7]
            / \
           2   1

Ici, la racine est un métanode composé de deux nœuds de valeur 8, et le premier métanode 8 est composé de deux métanodes 7.

À des fins de notation, le nœud "le plus à gauche" d'un métanode est le nœud le plus à gauche du métanode et le nœud "le plus à droite" d'un métanode est le nœud le plus à droite du métanode.

Dans cet arbre cartésien modifié, nous pouvons définir une marche en ordre des nœuds comme une marche qui visite tous les nœuds d'un méta-nœud dans l'ordre de gauche à droite, en effectuant une marche en ordre de chacun des nœuds qu'il contient. Nous imposons ensuite que l'arbre cartésien modifié a strict max-heap (chaque nœud doit être strictement plus grand que n'importe lequel de ses enfants) et qu'une marche en ordre de l'arbre donne les valeurs dans le même ordre que celui dans lequel elles apparaissent dans la séquence originale.

Remarquez que cette construction généralisée contient notre solution originale comme un cas spécial - si toutes les valeurs sont distinctes, rien n'est différent dans cette structure arborescente. Je vais également affirmer sans preuve qu'il est possible de construire une de ces structures en O(n) par une modification directe de l'algorithme standard des arbres cartésiens.

Dans cette structure arborescente modifiée, une plage de valeurs sans valeurs intermédiaires au moins aussi grande que les points d'extrémité correspond à l'un ou l'autre :

1. Un parent et le nœud le plus à droite de son enfant gauche.
2. Un parent et le nœud le plus à gauche de son enfant de droite.
3. Deux nœuds adjacents dans le même métanode.

La preuve des deux premières revendications est une modification assez simple de la preuve du cas précédent. La différence est qu'au lieu que la preuve de contradiction dise que cela violerait la propriété max-heap, on dirait plutôt que cela viole la propriété max-heap forte. Vous diriez également que toutes les valeurs égales au milieu de la plage devraient se manifester comme des nœuds qui empêcheraient les extrémités de la plage d'être les nœuds les plus à gauche ou les plus à droite dans un métanode. La preuve de la troisième affirmation est (en gros) que tous les nœuds entre les deux nœuds doivent être strictement plus petits que les extrémités, et s'il y avait une valeur égale au milieu, alors les deux nœuds ne seraient pas des métanœuds adjacents.

Compte tenu de cette observation, nous pouvons résoudre le problème original en temps O(n) comme suit. Tout d'abord, on construit un arbre cartésien généralisé à partir de la plage d'entrée. Ensuite, parcourez l'arbre et examinez toutes les paires d'éléments indiquées qui pourraient constituer la plage, en choisissant la plus grande que vous trouvez. Puisque pour chaque nœud, seul un nombre constant d'autres nœuds doit être vérifié (son parent, ses frères et sœurs de gauche et de droite, et ses enfants donnent au maximum cinq nœuds à vérifier), ceci peut être fait en O(n) temps pour un temps d'exécution net de O(n).

Ouf ! C'était un problème génial. Je ne sais pas si c'est une solution idéale, mais cela prouve au moins qu'il est possible de le faire en O(n) temps. Si quelqu'un trouve une meilleure solution, j'aimerais bien la voir.

Answer 2

Une solution simple basée sur la pile. On parcourt le tableau de gauche à droite, la pile contenant les éléments (techniquement, les index, mais on utilise les valeurs pour les comparaisons) qui sont soit.. :

1. Le plus grand à partir de la gauche (c'est-à-dire qu'il n'y a pas d'élément plus grand ou égal entre le début du tableau et l'élément).
2. Le plus grand depuis l'élément précédent sur la pile.

Lors du traitement de l'élément suivant x , les éléments pop plus petits que x pour autant qu'ils appartiennent à la catégorie 2. ci-dessus, alors poussez x sur la pile. Il est évident que vous devez conserver le maximum de courant pour pouvoir discerner entre la catégorie 2 et 1 en temps constant.

Le traitement ci-dessus est O(n) - chaque élément peut être poussé au maximum une fois et retiré au maximum une fois. En ayant la pile finale, il suffit de vérifier les paires voisines (sur la pile) - l'une des paires est la solution. Ceci aussi est O(n).

Voici une image de ce qui devrait rester sur la pile (les gros rectangles) après le balayage complet du tableau :

(Il y a une petite erreur dans l'image ci-dessus : la quatrième barre à partir de la gauche devrait être soit épaisse, soit dessinée plus courte que la première, désolé).

Pourquoi cela fonctionne : la pile finale contient tous les éléments du tableau d'entrée qui ne sont pas entre deux éléments plus grands (j'ai ignoré le cas d'un élément entre deux éléments égaux). La solution est évidemment une paire voisine de tels éléments.

Voici une implémentation en Python :

from collections import namedtuple

E = namedtuple('E', 'i x')

def maxrange(iterable):
    stack = [E(0, None)]*2 # push sentinel values
    maxsofar = None

    top = lambda: stack[-1] # peek at the top element on the stack

    for i, x in enumerate(iterable):
        while top().x < x and top().x < maxsofar:
            stack.pop()
        stack.append(E(i, x)) # push
        maxsofar = max(maxsofar, x)

    return max(b.i-a.i for a,b in zip(stack, stack[1:]))

Ejemplo:

>>> maxrange([2,1,3])
2

Answer 3

La solution de Rafal est bonne, mais nous pouvons nous passer de la pile et ainsi gagner un peu de mémoire. Voici une implémentation courte et efficace en O(n) temps :

def highDist(seq):
    res, ltr, rtl = 0, 0, 0
    for i in range(len(seq)):
        if seq[i] >= seq[ltr]:
            res = max(res, i-ltr)
            ltr = i
        if seq[-i-1] >= seq[-rtl-1]:
            res = max(res, i-rtl)
            rtl = i
    return res

Exécuter sur l'entrée d'exemple :

>>> print highDist([0, 10, 8, 9, 6, 7, 4, 10, 0])
6
>>> print highDist([0, 10, 8, 9, 6, 7, 4, 9, 0])
4
>>> print highDist([0, 10, 8, 9, 6, 7, 4, 7, 0])
2
>>> print highDist([])
0

L'astuce est que, si nous avons deux points a y b s.t. tout ce qui se trouve entre elles est plus petit qu'elles, alors la distance maximale que nous recherchons est soit |b-a| ou entièrement en dehors de la fourchette. Par conséquent, si l'on partitionne la séquence entière de cette manière, l'une d'entre elles est la plage que nous recherchons.

Nous pouvons faire la partition facilement en créant une séquence ascendante à partir de chaque extrémité.

Answer 4

Je ne suis pas sûr que la solution suivante soit O(n), mais elle est certainement "presque O(n)", et aussi très simple, juste quelques lignes de code. Elle est basée sur l'observation suivante. Pour toute paire d'indices (i,j), on trace un arc entre eux si l'intervalle [i,j] a la propriété recherchée. Observez maintenant qu'il est possible de tracer ces arcs de manière à ce qu'ils ne se croisent pas. Observez ensuite que les plus petites paires sont (i,i+1) - elles ont toutes la propriété recherchée. Ensuite, une paire plus grande peut toujours être construite par contraction de deux paires plus petites. Cela conduit à la structure suivante : Commencez par les paires (i,i+1) dans une liste liée. Passez en revue la liste liée de manière répétée, et essayez de contracter les liens consécutifs. Cet algorithme est indépendant de l'ordre en raison de la propriété de non-intersection. Le code Perl suit.

#!/usr/local/bin/perl -w
use strict;

my @values    = (0, 10, 8, 9, 6, 7, 4, 10, 0);           # original example.
@values       = map { int(100 * rand()) } 1..100;        # random testing.
my $nvalues   = @values;
my @intervals = (1..$nvalues-1);       # this encodes a linked list 0->1, 1->2, N-2->N-1

my $change = 0;
my ($maxi, $maxj) = (0, 1);            # initial solution
my $maxdelta = 1;

do {
   my ($jstart, $j) = (0, $intervals[0]);
   $change = 0;
   while ($j < $nvalues-1) {
      my $jnext = $intervals[$j];
      while ($jnext < $nvalues -1 && $values[$j] == $values[$jnext]) {
          $jnext = $intervals[$jnext];   # lookahead to skip intervals with identical boundaries
      }
      if ($values[$j] < $values[$jstart] && $values[$j] < $values[$jnext]) {
         $intervals[$jstart] = $jnext;                   # contraction step
         print STDERR "contraction to $j $jnext\n";
         $change = 1;
         $j = $jnext;
         if ($jnext - $jstart > $maxdelta) {
            $maxdelta = $jnext - $jstart;
            ($maxi, $maxj) = ($jstart, $jnext);
         }
      }
      else {
         ($jstart, $j) = ($j, $intervals[$j]);
      }
   }
   print STDERR "---\n";
}
while ($change);

my $jstart = 0;

while ($jstart < $nvalues -1) {
   my $jnext = $intervals[$jstart];
   local $, = " ";
   print STDERR @values[$jstart..$jnext], "\n";
   $jstart = $jnext;
}

print STDERR "solution $maxi $maxj\n";

Answer 5

ETA : J'ai trouvé quelques erreurs, désolé. Je vais y revenir après le travail, c'est définitivement un problème intriguant.

Écrit en pseudo-code, l'idée est de déplacer une fenêtre de trois nombres sur le tableau et d'effectuer certaines comparaisons, puis de mettre à jour vos positions gauche et droite en conséquence.

// Define the initial window
w1=a[0], w2=a[1], w3=a[2]
// Will hold the length of the current maximum interval
delta_max = 0

// Holds the value of the current interval's leftmost value
left=max(w1,w2,w3)
// Holds the position of the current interval's leftmost value
lpos= *position of the chosen wi above*

// Holds the position of the current interval's rightmost value
rpos = lpos + 1
// Holds the value of the current interval's rightmost value
right = a[rpos]

i = 0
// Holds the position of the max interval's leftmost value
lmax = 0
// Holds the position of the max interval's rightmost value
rmax = 0

while (i<n-3) do
    i = i + 3
    w1=a[i], w2=a[i+1], w3=a[i+2]

    if (w1<left) and (w2<left) and (w3<left)
        right = w3
        rpos = i + 2
    else
        // Set the new left to the first value in the window that is bigger than the current left
        if (w1>left): left = w1, lpos = i
        else
            if (w2>left): left = w2, lpos = i+1
            else
                if (w3>left): left = w3, lpos = i+2

    delta = rpos-lpos
    if delta>dmax: dmax = delta, lmax = lpos, rmax = rpos
    lpos = rpos
    rpos = lpos + 1
    right = a[rpos]
end