python - HackerRank 挑战 : Find total number of days Plants die

Question

Problem Statement

There are N 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.

Input Format

The input consists of an integer N. The next line consists of N integers describing the array P where P[i] denotes the amount of pesticide in plant i.

Constraints

1 ≤ N ≤ 100000
0 ≤ P[i] ≤ 109

Output Format

Output a single value equal to the number of days after which no plants die.

Sample Input

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.

挑战链接: HackerRank : Poisonous Plant

我的提交: HackerRank Submission Link

失败的测试用例 1: Input Output

失败的测试用例 2: Input Output

到目前为止我的代码:

total = int(raw_input())
plants = map(int,raw_input().split())
num_deaths = 1
day = 0
while num_deaths > 0:
    num_deaths = 0
    temp_plants = []
    day += 1
    for i in range(1, len(plants)):
        if plants[i] > plants[i - 1]:
            num_deaths += 1
            continue
        else:
            temp_plants.append(plants[i])
    plants = temp_plants
print(day - 1)

它仍然无法通过一些测试用例。有什么建议/建议吗？

Answer 1

查看您的 Temp_plants 数组，您使用 [] 对其进行了初始化。但是，由于您是从索引 1 开始迭代，因此始终排除索引 0 中的植物，因此您必须使用 [plant[0]] 进行初始化，因为最左边的植物始终包含在内。

示例:1 5 4 3 2

实际过程

• 1 5 4 3 2
• 1 4 3 2
• 1 3 2
• 1 2
• 1

回答=4

您的代码

• 1 5 4 3 2
• 4 3 2 [注意排除最左边的1]

回答=1

这是一个可以产生正确输出但速度相当慢的工作代码。它是正确的，但是 O(n^2) 使某些测试用例超时。这与您的算法基本相同。

n= input()
plant=map(int,raw_input().split())
count=0

# At each iteration the following loop updates the plant  
# list by removing weak plants and count counts no. of steps
# temp temporarily stores surviving plants

while(True):
    temp=[plant[0]]
    for i in range(1,len(plant)):
        if plant[i]<=plant[i-1]:    
             temp.append(plant[i])

# If temp and plants have same len, then no plant has
# been removed, so, the process ended.
    if(len(temp)==len(plant)):    break

    plant=temp
    count+=1

print count

我正在考虑一种应该可行的更快的动态方法，但尚未实现。