https://www.hackerrank.com/challenges/poisonous-plants
This challenge was really hard. I could not figure it out for a long time. The part with the stack is pretty obvious, but I missed the fact that older plants can have higher daysAlive values.
https://www.hackerrank.com/rest/contests/countercode/challenges/poisonous-plants/hackers/Kirhog/download_solution
http://www.cnblogs.com/tonix/p/4996518.html
There are plants in a garden. Each of these plants has been added with some amount of pesticide. After each day, if any plant has more pesticide than the plant at its left, being weaker than the left one, it dies. You are given the initial values of the pesticide in each plant. Print the number of days after which no plant dies, i.e. the time after which there are no plants with more pesticide content than the plant to their left.
7
6 5 8 4 7 10 9
Sample Output
2
Explanation
Initially all plants are alive.
Plants = {(6,1), (5,2), (8,3), (4,4), (7,5), (10,6), (9,7)}
Plants[k] = (i,j) => jth plant has pesticide amount = i.
After the 1st day, 4 plants remain as plants 3, 5, and 6 die.
Plants = {(6,1), (5,2), (4,4), (9,7)}
After the 2nd day, 3 plants survive as plant 7 dies. Plants = {(6,1), (5,2), (4,4)}
After the 3rd day, 3 plants survive and no more plants die.
Plants = {(6,1), (5,2), (4,4)}
After the 2nd day the plants stop dying.
http://www.martinkysel.com/hackerrank-poisonous-plants-solution/Plants = {(6,1), (5,2), (8,3), (4,4), (7,5), (10,6), (9,7)}
Plants[k] = (i,j) => jth plant has pesticide amount = i.
After the 1st day, 4 plants remain as plants 3, 5, and 6 die.
Plants = {(6,1), (5,2), (4,4), (9,7)}
After the 2nd day, 3 plants survive as plant 7 dies. Plants = {(6,1), (5,2), (4,4)}
After the 3rd day, 3 plants survive and no more plants die.
Plants = {(6,1), (5,2), (4,4)}
After the 2nd day the plants stop dying.
This challenge was really hard. I could not figure it out for a long time. The part with the stack is pretty obvious, but I missed the fact that older plants can have higher daysAlive values.
class
Plant:
def
__init__(
self
, pesticide, days):
self
.pesticide
=
pesticide
self
.days
=
days
def
solvePlants(a):
stack
=
[]
maxDaysAlive
=
0
for
pesticide
in
a:
daysAlive
=
0
while
stack
and
pesticide <
=
stack[
-
1
].pesticide:
daysAlive
=
max
(daysAlive, stack.pop().days)
if
not
stack:
daysAlive
=
0
else
:
daysAlive
+
=
1
maxDaysAlive
=
max
(maxDaysAlive, daysAlive)
stack.append(Plant(pesticide, daysAlive))
print
maxDaysAlive
def
main():
N
=
input
()
numbers
=
map
(
int
,
raw_input
().split())
solvePlants(numbers)
https://www.hackerrank.com/rest/contests/countercode/challenges/poisonous-plants/hackers/Kirhog/download_solution
http://www.cnblogs.com/tonix/p/4996518.html