Kolejna Większa Liczba

Dana jest tablica. Kolejną Większą Liczbą liczby x jest najbliższa (przeglądając kolejne elementy w prawą stronę) większa od niej liczba występująca w tablicy. Jeśli KWL dla x nie istnieje, wypisz -1 dla tego numeru. Należy założyć, że tablica jest “cykliczna”, tzn po osiągnięciu ostatniego elementu wyszukiwanie kontynuowane jest od indeksu 0.

Wejście: [1, 2, 1, 4, 1]
Wyjście: [2, 4, 4, -1, 2]

Zgodnie z: https://stackoverflow.com/questions/19720349/find-next-higher-element-in-an-array-for-each-element
udało mi sie napisać taki kod:

#include <iostream>
#include <stack>
#include <vector>

int get(std::stack<int> &s){
	int x = s.top();
	s.pop();
	return x;
}

int main(){
	
	std::stack<int> s;
	std::vector<int> data{1,2,1,4,1};

	s.push(data.at(0));
	data.erase(data.begin());
	for(int x : data){
		if(!s.empty()){
			while(true){
				if(s.empty() || s.top() > x){
					break;
				}

				std::cout << get(s) << " : " << x << std::endl;
			}
		}

		s.push(x);
	}

	while(!s.empty()){
		std::cout << get(s) << " : -1\n";
	}

	return 0;
}

Jednak daje złą odpowiedź oraz jest jakoś porozwalane

Prosze o pomoc

Zestaw sobie data.erase(data.begin()); z Należy założyć, że tablica jest “cykliczna”.

Edit: strasznie to wszystko przekomplikowałeś tak w ogóle: https://ideone.com/Y53Bqw.

Zmieniłem kod

nadal to samo. A Twój kod to jest zwykły bruteforce w n^2. Chciałbym, żeby to działało w czasie liniowym

W sumie zrobiłem teraz coś takiego:

#include <iostream>
#include <stack>
#include <vector>

typedef std::pair<int, int> item;

item get(std::stack<item> &s){
	item x = s.top();
	s.pop();
	return x;
}

int main(){
	
	std::stack<item> s; //index, val
	std::vector<int> data{1,2,1,4,1}; //[2, 4, 4, -1, 2]
	int size = data.size();
	std::vector<int> o(size);

	s.push(std::make_pair(0, data.at(0)));
	for(int i = 1; i < size-1; i++){
		int x = data[i];
		if(!s.empty()){
			while(true){
				if(s.empty() || s.top().second > x){
					break;
				}
				o.at(get(s).first) = x;
				//std::cout << i.second << " : " << x << std::endl;
			}
		}

		s.push(std::make_pair(i, x));
	}

	while(!s.empty()){
		o.at(get(s).first) = -1;
		//std::cout << i.second << " : -1\n";
	}

	o.at(size-1) = -1;
	for(int i = 0; i < size-1; i++){
		if(data[i] > data[size-1]){
			o.at(size-1) = data[i];
			break;
		}
	}

	std::cout << '\n';

	for(int i = 0; i < size; i++){
		std::cout << data[i] << " : " << o[i] << '\n'; 
	}

	return 0;
}

I działa, ale dla ostatniego przechodze całą tablice, nie wiem jak inaczej to zrobić. Troche lamersko ....

Ależ ja dawno w C++ nie pisałem :D

#include <iostream>
#include <stack>
#include <vector>

int main() {

	std::stack<int> stackOfIndexes;
	std::vector<int> data{ 1,2,1,4,1 };
	std::vector<int> result(data.size());
	std::fill(result.begin(), result.end(), -1);
	std::vector<int> doubleData = data;
	copy(data.begin(), data.end(), back_inserter(doubleData));
	
	for (int i = 0; i < doubleData.size(); ++i)
	{		
		while (!stackOfIndexes.empty() && doubleData[stackOfIndexes.top()] < doubleData[i])
		{
			result[stackOfIndexes.top()] = doubleData[i];
			stackOfIndexes.pop();
		}

		if (i < data.size())
		{
			stackOfIndexes.push(i);
		}
	}

	for (int i = 0; i < data.size(); ++i)
	{
		std::cout << data[i] << " : " << result[i] << std::endl;
	}	

	return 0;
}

A mógłbyś wyjaśnić na czym polega ten sposób?

To jest dokładnie zmodyfikowany Twój kod implementujący rozwiązanie ze stackoveflow.
Plus dodałem dwa tricki, które uprościły znacznie kod:

• "ale dla ostatniego przechodzę całą tablice, nie wiem jak inaczej to zrobić.", inaczej można to zrobić przez skopiowanie oryginalnej tablicy x2, dzięki temu mamy jedną pętle przechodzącą dwa razy tą samą tablicę, zauważ że trochę inaczej przetwarzamy pierwszą połowę/kopię od drugiej połowy/kopi - nie dodajemy już wtedy na stos
• zamiast trzymać wartości, czy pary na stosie, wystarczy nam indeks z oryginalnej tablicy zawierającej dane wejściowe

złożoność O(3*n)

template<typename It, typename F>
auto cycle_find_if(It b, It e, It start, F &&f) -> It
{
    auto i = std::find_if(start, e, f);
    if (i != e) return i;
    i = std::find_if(b, start, std::forward<F>(f));
    return i != start ? i : e;
}

int cycleFindFirstGreater(const std::vector<int>& v, int index)
{
    auto x = v[index];
    auto it = cycle_find_if(v.begin(), v.end(), v.begin() + index, [x](auto a) { return a > x; });
    return it != v.end() ? *it : -1;
}