use stack to pop out the max num under O(1)

Question

Sigiloso · Accepted Answer

my way is too complex... 
Good answer would be using Class or 2 stacks, and keep record the current max

Sigiloso · Answer

Using c++ and 2stack
#include 
#include 

std::stack S;

void addToStack(int value)
{
	std::stack T;

	while(!S.empty() && (S.top() > value)) {
		int V = S.top();
		T.push(V);
		S.pop();
	}
	S.push(value);
	while(!T.empty())
	{
		S.push(T.top());
		T.pop();
	}
	

}

int getMaxValue()
{
	int value = S.top();
	S.pop();
	return value;
}

int main()
{
	addToStack(17);
	addToStack(15);
	addToStack(4);
	addToStack(16);
	addToStack(1);

	int max = getMaxValue();
	std::cout << max << std::endl;
}

Meta

Pergunta de entrevista da empresa Meta

Respostas da entrevista

Empresas seguidas

Buscas de vagas