MOOC《北京大学——データ構造とアルゴリズムPython版》第四週OJ作業2:最近の要求回数

2.最近のリクエスト回数(10分)
タイトル内容:
各イベントが発生した場合、10000ミリ秒以内に発生したイベントの数を計算します.すなわち、リスト内の各要素kについて、k - 10000とk(両端ともに含む)の間にリスト全体にどれだけの要素があるかを算出する.
入力形式:
並べ替えられたリストmylistで、すべての要素は非負の整数であり、各要求の発生時間をミリ秒単位で記録する.
出力フォーマット:mylistと等しいリスト.
サンプルを入力:[0,10,100,1000,10000,20000,100000]
出力サンプル:[1,2,3,4,5,2,1]
時間制限:500 msメモリ制限:32000 kb
問題の分析:
リストが整列しているため、操作キューは、キューヘッダ要素とキューヘッダ要素との差が10000以内にあるようにする.すなわち、リスト全体を遍歴し、1つの要素に遍歴するたびにappendをキューの最後に入力し、小さすぎる(10000差を超えた)キューヘッダ要素をすべてキューから出す.このときキューの長さは出力するデータ項目であり,outputリストに押し込む.外部クラスdeque:from collections import dequeをインポート
アルゴリズムの特殊な状況:
ここには穴があります.多くの要素がつながっている可能性があります.値は同じです.この場合,キュー内の要素だけでなく,後の等しい要素も計算する.処理方法は、1つの要素iに遍歴するたびに、その後ろの要素が変わらないかどうかを判断し、jで表され、最初の要素より大きい要素まで遍歴する.このときキューの長さは、i~jの間のすべての要素のoutputデータ項目である.
AC:Pythonコード

from collections import deque
def func(mylist):
    # your code here
    output = []
    dq = deque()
    
    i = 0
    while i < len(mylist):
        dq.append(mylist[i])
        while len(dq) > 0 and mylist[i] - dq[0] > 10000:
        	# dq[0]    ，dq[-1]    
            dq.popleft()
        j = i + 1
        while j < len(mylist) and mylist[j] == mylist[i]:
            dq.append(mylist[j])
            j += 1
        while i < j:
            output.append(len(dq))
            i += 1
    return output

mylist = eval(input())
print(func(mylist))