为什么有毒植物的堆积液会产生毒性？

Question

正在尝试解决hackerrank问题。在

花园里有植物。这些植物每种都加了一定量的杀虫剂。每天过后，如果任何一种植物的杀虫剂比左边的植物多，比左边的弱，它就会死亡。你会得到每种植物中杀虫剂的初始值。打印出没有植物死亡的天数，也就是说，在这之后没有比左边的植物含有更多农药的植物的时间。在

我用堆栈来解决这个问题。示例如下：

a = 6 5 8 4 7 10 9

10 > 9   a = 6 5 8 4 7 10    b = 9

7 > 10   a = 6 5 8 4 7       b = 9

4 > 7    a = 6 5 8 4         b = 9

8 > 4    a = 6 5 8           b = 9 4

5 > 8    a = 6 5             b = 9 4

6 > 5    a = 6 5             b = 9 4

在此之后，只需使用a = a + b.reverse()创建一个新列表。再次启动该过程，并在列表按相反顺序排序时退出。在

这还是让我的时间超过了。有什么想法吗？在

^{pr2}$

编辑代码：

^{3}$

Answer 1

我同意Woot4Moo的观点，有些东西看起来不太对劲，我建议你多关注栈的使用（而不是双链表）。请参见this link to the Stock Span problem，它有助于详细说明跟踪价格列表中差异的O(N)解决方案。这可以通过添加杀虫剂的条件加以扩展。在

例如，它将填补以下空白：

import sys

ps = [int(s) for s in list(sys.stdin)[1].strip().split()]
stack = [ps[0]]
max_days = 0
for i in range(1, len(ps)):
    days[i] = 1 if ps[i] > ps[i-1] else 0

    # TODO - Logic to update days[i] 
    while len(stack) > 0 and ps[i] <= stack[-1][1]:
        (ps_other, days_other) = stack.pop()

    stack.append((ps[i], days[i])
    max_days = max(max_days, days[i])

print(max_days)

我很快在O(N^2)中实现，发现80%的测试通过（其余的超时），因此根据上面的链接更巧妙地使用堆栈应该可以完成这项工作。在

^{pr2}$

---

编辑：请注意系统标准HackerRank用于测试输入。在

Answer 2

排序是N log N，我觉得你的数据结构不对。为什么不使用双链表，因为要求它是最左边的邻居。你可以简单地取消引用死去的指针。在