题解 | #最小活动范围#

• 题目考察的知识点 : 单调队列
• 题目解答方法的文字分析：

1. 维护一个单调不降的队列 q ，其中队首元素对应的小时区间最小活动范围最大（即最优解）
2. 如果当前队尾元素到当前位置的距离大于等于 k，则将队首元素出队；
3. 重复步骤 1 直到队首元素到当前位置的距离小于 k；
4. 将当前位置加入队尾；
5. 如果当前位置减去队首位置大于等于 k，则将队首元素出队。
6. 由于要求连续的 k 个小时内的最小活动范围，因此在前 k - 1 个小时内无法得到答案，所以需要等到第 k 个小时才开始输出结果。

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @param k int整型
# @return int整型一维数组
#
import collections
class Solution:
    def minSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        q = collections.deque()
        res = []

        for i in range(n):
            while q and i - q[0][0] >= k:
                q.popleft()
            while q and nums[i] < q[-1][1]:
                q.pop()
            q.append((i, nums[i]))
            if i >= k - 1:
                res.append(q[0][1])

        return res