Codility - Closest ascenders - rozwiązanie.

Codility umożliwia dla programistów certyfikowanie samych siebie, czyli wchodzisz na stronę, rozwiązujesz podany problem i możesz szczycić się certyfikatem Codility... do czasu wystawienia następnego zadania :)
Poniżej chciałbym opisać sposób rozwiązania zadania polegającego na poszukiwaniu najbliższej większej wartości w tablicy intów (closest ascenders). Zadanie to zaliczyłbym do trudnych, ale pewnie tylko dlatego...
że nie udało mi się go rozwiązać w regulaminowym czasie :)
Ale jako, że porażkami chwalić się nie można przejdźmy do tego, że w końcu problem rozwiązałem :)

Czyli mamy daną tablicę obiektów typu int (int[] A) i mamy dla każdej wartości z tej tablicy znaleźć indeks najbliższej, większej od niej wartości tzw. "closest ascender".

           if K has the closest ascender J, then R[K] = abs(K−J); that is, R[K] is equal to the distance between J and K,
           if K has no ascenders then R[K] = 0.

Maksymalna złożoność algorytmu to po raz kolejny O(n) - czyli liniowa!

Jak wiadomo każdy z elementów może mieć "ascender'a" z lewej i prawej strony (oprócz elementów skrajnych), więc rozpatrzymy zadanie na dwa kierunki poszukiwań (od lewej do prawej i odwrotnie) a potem "skleimy" wyniki.

Iterując po tablicy A, możemy przetrzymywać wszystkie "ascender'y", które wystąpiły wcześniej (przed aktualnym indeksem tablicy) na stosie.
Jeżeli element tablicy przetrzymywany na stosie przestaję być "ascender'em", czyli nie jest większy od wartości znajdującej się pod aktualną pozycją tablicy, to zabieramy go ze stosu oraz wszystkie inne nie będące "ascender'ami".
Różnicę pomiędzy aktualną pozycją a indeksem ostatniego elementu na stosie umieszczamy w częściowej tablicy wynikowej (częściowej bo rozbiliśmy obliczenia na dwa kierunki).
Gdy "ascender'a" nie znajdziemy to w tablicy wynikowej wstawiamy 0.

 
        int[] LeftToRightR = new int[A.Length];
        Stack<int> ascendersOnly = new Stack<int>();
        for(int i = 0; i < A.Length; i++)
        {
            while (ascendersOnly.Count != 0 && A[ascendersOnly.Peek()] <= A[i])
                ascendersOnly.Pop();//remove because is not ascender
            if (ascendersOnly.Count == 0)
                LeftToRightR[i] = 0;//ascender not found
            else
                LeftToRightR[i] = i - ascendersOnly.Peek();//found ascender
            ascendersOnly.Push(i);
        }

Połowa rozwiązania za nami. Druga część jest podobna tylko iteracja przebiega w odwrotnym kierunku. Najpierw czyścimy stos.

ascendersOnly.Clear();

Następnie szukamy "ascender'ów" od prawej do lewej lub z góry na dół jak kto woli.
Zwróćcie uwagę na to, że gdy znajdziemy "ascender'a" to wstawiamy "odwrotną" różnicę indeksów niż w poprzednim przypadku.

        for (int i = A.Length - 1; i >= 0; i--)
        {
            while (ascendersOnly.Count != 0 && A[ascendersOnly.Peek()] <= A[i])
                ascendersOnly.Pop();//remove because is not ascender
            if (ascendersOnly.Count == 0)
                RightToLeftR[i] = 0;//ascender not found
            else
                RightToLeftR[i] = ascendersOnly.Peek() - i;//found ascender
            ascendersOnly.Push(i);
        }

Gdy częściowe tablice wynikowe są już obliczone należy je "skleić". Wybieramy mniejszą z wartości częściowych, chyba że jest ona 0 co oznacza, że "ascender'a" nie znaleziono. W takim wypadku wybieramy drugą wartość.

        for(int i = 0; i < A.Length; i++)
        {
            R[i] = LeftToRightR[i] == 0 ? RightToLeftR[i] :
                    RightToLeftR[i] == 0 ? LeftToRightR[i] :
                    Math.Min(RightToLeftR[i], LeftToRightR[i]);
        }

Parametry testowe zadania podane przez autorów jak ktoś będzie chętny, żeby mnie sprawdzić.

            int[] A = new int[] { 4, 3, 1, 4, -1, 2, 1, 5, 7 };
            int[] R= new int[] {7, 1, 1, 4, 1, 2, 1, 1, 0 };

Rozwiązanie gotowe, problem zniknął, więc wracajmy do "real'u".