爲什麼有毒植物堆棧解決方案給予TLE？

花園裏有植物。每種植物都添加了一定量的農藥。每天之後，如果任何一種植物比左側的植物含有更多的農藥，比左側的植物弱，則會死亡。你會得到每種植物中農藥的初始值。打印沒有植物死亡的天數，即沒有植物的農藥含量高於植物左邊的植物的時間。

我已經使用堆棧來解決這個問題。下面的例子：

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()。當列表按相反順序排序時，再次啓動該過程並退出。

這仍然給我超時。任何想法？

n = int(input()) 
first_list = input().split() 
first_list = [int(i) for i in first_list] 
count = 0 
second_list = [] 
data_1, data_2 = 0, 0 
while True: 
    b = [] 
    if sorted(first_list, reverse=True) == first_list: 
    break 
    data_1 = first_list.pop() 
    for i in range(len(first_list)-1): 
    data_2 = first_list.pop() 
    if data_1 > data_2: 
     pass 
    elif data_1 < data_2: 
     second_list.append(data_1) 
    elif data_1 == data_2: 
     second_list.append(data_1) 
     second_list.append(data_2) 
    data_1 = data_2 
    if len(first_list)>=1 and data_1 < first_list[0]: 
    first_list.append(data_1) 
    second_list.reverse() 
    first_list = first_list + second_list 
    count += 1 
print(count)

編輯的代碼：

n = int(input()) 
input = [int(i) for i in input().split()] 
count, t_length = 0, 0 
cmp = input[0] 
while True: 
    length = len(input) 
    for i in range(1, length): 
    if input[i] == -1: 
     t_length += 1 
     continue 
    if input[i] > cmp: 
     cmp = input[i] 
     input[i] = -1 
    else: 
     t_length += 1 
     cmp = input[i] 
    if t_length+1 == length: 
    break 
    count += 1 
    cmp, t_length = input[0], 0 
print(count)

來源

2016-05-13 noman pouigt

當你使用'a'和'b'這些無意義的變量名時，hackerrank會給出更好的分數嗎？如果不是，你爲什麼這樣做？ – Barmar

這看起來至少是O（n^2）[如果用線性時間檢查來替換這些排序]。鑑於輸入列表的長度可能爲10萬年，也許你需要放棄使用簡單方法解決問題並找到更智能方法的想法？ –

鏈接列表不會改變（據我所知）關於算法工作原理的任何基礎知識，儘管它看起來像一個有希望的方式來加快代碼的速度 - 儘管您可能會使用相同的方法一個常規數組，並在迭代某個特定日期的值時在原位刪除元素。當然，你不想每次都進行排序。很難知道任何優化是否足以讓您的代碼足夠快地通過hackerrank測試。我猜他們不是，但這取決於測試輸入是否特別討厭。 –

我同意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％通過（其餘超時），所以更巧妙地使用堆棧根據上面的鏈接應該做的工作。

import collections 
import sys 

ps = [int(s) for s in list(sys.stdin)[1].strip().split()] 
ps_prev = [] 
days = 0 
while collections.Counter(ps_prev) != collections.Counter(ps): 
    ps_prev = ps[:] 
    i = len(ps) - 1 
    while i > 0: 
     if ps[i] > ps[i-1]: 
      ps.pop(i) 
     i -= 1    
    days += 1  

print(days - 1)

編輯：注意，粗略sys.stdin用途是迎合HackerRank測試輸入。

來源

2016-05-22 14:46:13 Kappers

排序是N log N和你的數據結構看來我錯了。爲什麼你不使用雙向鏈表，因爲要求它是最左邊的鄰居。你只需解除引用死亡的指針。

來源

2016-05-13 02:13:53 Woot4Moo

@nomanpouigt「你的數據結構怎麼看起來對我來說不對」然後我解釋一下使用神祕的數據結構？ – Woot4Moo

@nomanpouigt所以你的代碼超時正確，因此TLE？你正在對你的堆棧進行不必要的排序。雙鏈表解決方案將是N（不需要排序），並且不需要額外的存儲（除非您計算雙向鏈表的開銷）。 – Woot4Moo

我現在瞭解那部分。看起來我正在給這個問題提供不必要的信貸，因爲它很難。我可以簡單地用一個簡單的列表解決它，而不使用堆棧。在將此答案標爲正確之前，我會等待更多評論。 –

爲什麼有毒植物堆棧解決方案給予TLE？

回答

相關問題