プログラマスタック/キュー-株価


問題の説明


秒単位で記録された株価の配列価格をパラメータとして指定すると、価格が下がらない時間帯に数秒戻るように解く関数が完了する.

せいげんじょうけん


価格はそれぞれ1以上10000以下の自然数です.
価格の長さは2以上100000以下です.
I/O例
prices
[1, 2, 3, 2, 3]
return
[4, 3, 1, 1, 0]
I/O例説明
1秒の1はずっと値下げしていません.
2秒の2ずっと値下げしていません.
3秒ポイントの3は1秒後に値下げされます.そのため、価格は1秒以内に下がっていない.
4秒時の2は1秒以内に値下げされませんでした.
5秒時の3は0秒以内に値下げされませんでした.

プール(効率テストタイムアウト)

def solution(prices):
    answer = []
    answer.append(0)
    check = [0 for _ in range(len(prices))]
    for i in range(1, len(prices)):
        answer.append(0)
        for j in range(len(answer)-1):
            if prices[i] >= prices[j] and check[j] == 0:
                answer[j] += 1
            elif check[j] == 0:
                check[j] = 1
                answer[j] += 1
    return answer
  • iは秒、
  • 現在の価格が前の(j)と同じである場合、秒数が追加される.
  • 価格が下がった後、検査して固定します
    ->テストケースはすべて合格しましたが、効率テストタイムアウト

    他人を解く

    def solution(prices):
        answer =[0] * len(prices)
        for i in range(len(prices)):
            for j in range(i+1, len(prices)):
                if prices[i] <= prices[j]:
                    answer[i]+=1
                else:
                    answer[i]+=1
                    break
        return answer
  • こんなに簡単...
  • iで
  • をつかんで今、iの後ろから順番に回って、自分より小さいのが現れるまで.
  • スタッキング

  • この問題はスタックで解決するとより効率的です.
  • def solution(prices):
        answer = [0]*len(prices)
        stack = []
     
        for i, price in enumerate(prices):
            #stack이 비었이면 false
            # 스택 마지막 값이 현재 가격보다 크면 -> 가격이 떨어졌다는 의미 -> pop
            while stack and price < prices[stack[-1]]:
                j = stack.pop()
                answer[j] = i - j
            stack.append(i)
     
        # for문 다 돌고 Stack에 남아있는 값들 pop
        while stack:
            j = stack.pop()
            answer[j] = len(prices) - 1 - j
     
        return answer
    回転ドア
  • .i現在
  • 秒目
  • スタック有価で、スタックの最後の値は現在の価格より大きく、価格が
  • 下がったことを意味します.
  • スタックでpopを行うことは、固定時間を意味する
    スタックが
  • スタックになる前にスタックの最後の値を現在の価格と比較し、価格が下がるとスタックの最後の値をjに入れ、現在の時間(i)-jをresponse[j]に入れて固定する.
  • prices [1,2,3,2,3]
    answer [0,0,0,0,0]
  • を整理し、スタックに現在の時間を蓄積し続けます.
    [0,1,2]
  • 価格は
  • 3秒から下がった.
    [0,1] >>pop>> 2 , answer[2] = 3 - 2 => answer[0,0,1,0,0]
  • [0,1,3,4]以降は下降することなくスタック上に直接積み上げる
  • .
  • スタックの数字は、時間単位の
  • です.
  • ではresponse[j]のようにjはインデックスであり,j+1招待保持時間といえる.
  • によれば,全員がjを取り出して[j]=(総時間−1)−jと答えた.