[伯俊]10003:最高価格を探す
809 ワード
スライドウィンドウ+インデックス
さいこうをさがす
これはスライドウィンドウの問題です.import sys
from collections import deque
input = sys.stdin.readline
n, l = map(int, input().split())
lst = list(map(int, input().split()))
q = deque()
# 맨 처음 값 Di = Ai-L+1 ~ Ai 은 i <= 0은 무시되기 때문에 현재 리스트에 담긴 값의 맨 처음값임
q.append([lst[0], 0])
print(q[0][0], end = ' ')
# 1. 큐의 맨 뒷값이 현재 값보다 크다면 pop()
2. l의 범위를 넘는다면 pop()
3.리스트의 맨 앞값이 가장 작은 값임
for i in range(1, len(lst)):
while q and q[-1][0] > lst[i]:
q.pop()
while q and q[0][1] < i - l + 1:
q.popleft()
q.append([lst[i], i])
print(q[0][0], end = ' ')
Reference
この問題について([伯俊]10003:最高価格を探す), 我々は、より多くの情報をここで見つけました
https://velog.io/@jinii/백준-11003-최솟값-찾기
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
import sys
from collections import deque
input = sys.stdin.readline
n, l = map(int, input().split())
lst = list(map(int, input().split()))
q = deque()
# 맨 처음 값 Di = Ai-L+1 ~ Ai 은 i <= 0은 무시되기 때문에 현재 리스트에 담긴 값의 맨 처음값임
q.append([lst[0], 0])
print(q[0][0], end = ' ')
# 1. 큐의 맨 뒷값이 현재 값보다 크다면 pop()
2. l의 범위를 넘는다면 pop()
3.리스트의 맨 앞값이 가장 작은 값임
for i in range(1, len(lst)):
while q and q[-1][0] > lst[i]:
q.pop()
while q and q[0][1] < i - l + 1:
q.popleft()
q.append([lst[i], i])
print(q[0][0], end = ' ')Reference
この問題について([伯俊]10003:最高価格を探す), 我々は、より多くの情報をここで見つけました https://velog.io/@jinii/백준-11003-최솟값-찾기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol