なぜ毒性植物はTLEを与えるスタック溶液ですか？

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 

この後、で新しいリストを作成します。リストを逆の順序で並べ替えると、プロセスが再び開始され、終了します。

これはまだ私に時間を超えています。何か案が？

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) 

Answer 1

私はWoot4Mooに何かが正しく見えないことに同意しています。ダブルリンクリストの代わりにスタック使用にもっと集中することをお勧めします。価格リストの相違を追跡するためのO(N)ソリューションの詳細を示すthis link to the Stock Span problemを参照してください。これは農薬の条件で拡張することができます。

例えば、それはの隙間に充填されたい：

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) 

Iはすぐスタックを使用してので、より巧妙に、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テスト入力に対応するためであることに注意してください。

Answer 2

ソートはN log Nであり、あなたのデータ構造は、私には間違っているようです。なぜなら、最も左のネイバーであるという要件なので、なぜ二重リンクリストを使用しないのでしょうか。あなたは単に死んだポインタを参照解除するだけです。