We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Just to supplement purnawirman's algorithm explanation.
http://algorithmsandme.in/2014/02/stacks-stock-span-problem/ This page gives an excellent illustration of the "stock span problem". This problem is similar to the stock span problem, but more complicated. The following is my C++ code, which passed all the test cases. Just for reference.
struct Node
{
int plantID; // we label plants from 0 to N - 1
int daysToDie; // the days a plant needs to die, -1 means it will not die
};
int main()
{
std::vector<int> pesticides;
int N;
std::cin >> N;
for (int i = 0; i < N; i++)
{
int pesiticide;
std::cin >> pesiticide;
pesticides.push_back(pesiticide);
}
std::stack<Node> s;
s.push({ 0, -1 });
int maxDaysToDie = -1; // the max days needed to die among all the plants
for (int i = 1; i < N; i++)
{
// we only care about the plants whose pesticide is smaller (potential killer)
int daysToDie = 1;
while (!s.empty())
{
if (pesticides[s.top().plantID] >= pesticides[i])
{
// need to wait the front plants to die, like "1 5 4", 4 will die only after 5 died
daysToDie = std::max(daysToDie, s.top().daysToDie + 1);
s.pop();
}
else // find the killer
{
break;
}
}
if (s.empty()) // this means no preceding plants have less pesticide than ith plant
{
daysToDie = -1;
}
maxDaysToDie = std::max(maxDaysToDie, daysToDie);
s.push({ i, daysToDie });
}
std::cout << (maxDaysToDie < 0 ? 0 : maxDaysToDie) << std::endl;
return 0;
}
Poisonous Plants
You are viewing a single comment's thread. Return to all comments →
Just to supplement purnawirman's algorithm explanation. http://algorithmsandme.in/2014/02/stacks-stock-span-problem/ This page gives an excellent illustration of the "stock span problem". This problem is similar to the stock span problem, but more complicated. The following is my C++ code, which passed all the test cases. Just for reference.