[プログラマー]株価Lv2 - Python

[プログラマー]株価Lv2
私の答え

def solution(prices):
    answer = [0] * len(prices)
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            answer[i] += 1
            if prices[i] > prices[j]:
                break
    return answer

キューです.これは最も簡単なスタックレスアクセスです.

価格が

の次のインデックスを下回った場合、終了します.あるいはもう1秒

キューを使用するプール

from collections import *
def solution(prices):
    queue = deque(prices)
    answer = []
    while queue:
        price = queue.popleft()
        sec = 0
        for s in queue:
            sec += 1
            if price > s:
                break
        answer.append(sec)
    return answer

キューを使用して、キュー内の要素が存在する場合に繰り返します.キューから最初の要素を取り出し、価格変数に入れます.

最初の要素を除いて、キューの周りを回転します.同様に、価格が価格より低い場合は、繰り返しを停止するか、sec+=1を続行します.

for家を出て、回答にsecを入れます.

の結果、同じ方法を採用しているので、性能の差は大きくないと思いますが、効率テストの結果は2倍ほど違います.

スタックを使用したプール

def solution(prices):
    stack = []
    answer = [i for i in range(len(prices) - 1, -1, -1)]
    for i in range(len(prices)):
        while stack and prices[stack[-1]] > prices[i]:
            sec = i - stack[-1]
            answer[stack.pop()] = sec
        stack.append(i)
    return answer

白駿の17298号大数問題とよく似ている.

株価が下落しなければ、答えは総要素の個数が3個であれば、2,1,0の形で現れる.そこで、まず問題がないと仮定し、答えを設定します.

スタック内の最後の要素の価格(i)よりも価格が低い場合、価格が下がったことを意味し、互いのインデックスの違いを求め、答えスタックを与えることができる.pop()インデックスに対応する値を入力します.

スタックが空であるか、次の価格がより大きい場合は、スタックにインデックスを追加します.

効率ではスタック速度が最も速い.