株価:レベル2 pisun

質問する

https://programmers.co.kr/learn/courses/30/lessons/42584

私の髪の草

def solution(prices):
    answer = [0 for i in range(len(prices))]
    
    i = 0
    while 1:
        now = prices[i]

        for j in range(i+1, len(prices)):
            if prices[j] < now:
                answer[i] = j - i
                break
            else:
                answer[i] += 1
        i += 1

        if i == len(prices) - 1:
            answer[i] = 0
            break

    return answer

✔提出の際、タイムアウトが出るかと思いましたが、パスしてくれて幸せでした.でも気分が悪くて.問題タイプのスタックやキューが使用されていないためかもしれません.ははは
でも好きな草も私の草とあまり差がありません.しかし、入力の大きさが大きくなると、非効率な答えのようです.

スタックプール

def solution(prices):
    stack = []
    answer = [0] * len(prices)

    for i in range(len(prices)):
        if stack != []:
            while stack != [] and stack[-1][1] > prices[i]:
                past, _ = stack.pop()
                answer[past] = i - past
        stack.append([i, prices[i]])

    for i, s in stack:  
        answer[i] = len(prices) - 1 - i

    return answer

最初はスタックでロックを解除したいと思っていました.しかし、スタックにpriceを挿入する方法だけでは、処理を必要とせずに値下げされた要素をどのように処理するかは解決できないと思います.
🔑 上図のように、stackにインデックスとpriceを加えて処理すれば解決します.
インデックスをスタックに配置する方法!