Die längste Teilarray, dass alle Elemente kleiner oder gleich A [i]

Question

I A[1,...,n] positiver Zahlen eine Anordnung haben, zum Beispiel:

[1, 2, 5, 3, 7, 2, 8, 4] 

Ich brauche ein Array S[1,...,n] nach der Definition zu erstellen:

S[i] = max {k|∀i−k <j≤i :A[j] ≤ A[i] and k ≤ i} 

Es bedeutet die längste Unterarray A[i − k,..,i], dass alle seine Elemente zu finden, die weniger oder gleich A[i] für jeden Index in der Anordnung.

Ich muss einen Algorithmus schreiben, der das Array S in O (n) mit Stack erstellt.

Zum Beispiel für das Array [1,2,4,3,5] Ich brauche das Array zurück [1,2,3,2,5]

Danke.

Answer 1

Sie können (current_maximum, size_of_sequence) im Stapel für jede Folge von steigenden Zahlen speichern. Bei jeder Iteration Sie Wert Sequenz sollte hinzufügen (optional verschmelzenden benachbarte Sequenzen, wenn neue Wert größer ist)

#include <stack> 
#include <vector> 
#include <utility> 

std::vector<int> leq_subarrays(const std::vector<int>& numbers) { 
    if (numbers.empty()) { 
    return std::vector<int>(); 
    } 
    std::vector<int> answer(numbers.size()); 
    std::stack<std::pair<int, int>> s; 
    s.push(std::make_pair(numbers[0], 1)); 
    answer[0] = 1; 
    for (size_t i = 1; i < numbers.size(); ++i) { 
    const auto& value = numbers[i]; 
    int count = 1; 
    while (!s.empty() && s.top().first <= value) { 
     count += s.top().second; 
     s.pop(); 
    } 
    s.push(std::make_pair(value, count)); 
    answer[i] = count; 
    } 
    return answer; 
} 

Link zu Ideone: http://ideone.com/SlZorX