水群得一题
脑子抽了,看滑动窗口不行没想单调栈硬贪心没贪出来
别人的正解:
from collections import deque
def solution(n, k, data):
ans=0
queue = deque()
for i in range(n):
while queue and data[queue[-1]] > data[i]:
queue.pop()
queue.append(i)
while queue[0] < i - k +1:
queue.popleft()
ans += data[queue[0]]
return ans
if __name__ == "__main__":
# Add your test cases here
print(solution(5, 2, [1, 2, 3, 3, 2]) == 9)