1. 面试题59 - I. 滑动窗口的最大值/239. 滑动窗口最大值
2. 面试题59 - II. 队列的最大值
3. 剑指 Offer 13. 机器人的运动范围

    

队列：普通队列满足，先进先出，目前也支持双端出的队列形式。

   

一、面试题59 - I. 滑动窗口的最大值/239. 滑动窗口最大值

1.1 问题

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

进阶：你能在线性时间复杂度内解决此题吗？

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3

输出: [3,3,5,5,6,7]

解释:

滑动窗口的位置 最大值

--------------- -----

[1 3 -1] -3 5 3 6 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7

提示：

1 <= nums.length <= 10^5

-10^4 <= nums[i] <= 10^4

1 <= k <= nums.length

1.2 解析

利用双向队列，按照递减的排序来做，滑动的过程中可能会剔除一些没有可能的小数字

1.3 代码

class Solution:

    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:

        if not nums or k == 0: return []

        deque = collections.deque()   #定义双向队列，两边都可以进出

        for i in range(k): # 未形成窗口

            while deque and deque[-1] < nums[i]: #保持deque是一个递减的数组

                deque.pop()

            deque.append(nums[i])  #根据上面的调整，插入新来的数，也能保持递减

        res = [deque[0]]  #将最前面的数插入加过中，因为此时就是最大的

        for i in range(k, len(nums)): # 形成窗口后

            if deque[0] == nums[i - k]: #如果最大值落在滑动窗口的左侧，要将其删除

                deque.popleft()

            while deque and deque[-1] < nums[i]: #保持deque是一个递减的数组

                deque.pop()

            deque.append(nums[i])

            res.append(deque[0])

        return res

二、面试题59 - II. 队列的最大值

2.1 问题

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。若队列为空，pop_front 和 max_value 需要返回 -1

示例 1：

输入:

["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]

[[],[1],[2],[],[],[]]

输出: [null,null,null,2,1,2]

示例 2：

输入:

["MaxQueue","pop_front","max_value"]

[[],[],[]]

输出: [null,-1,-1]

2.2 代码

import queue

class MaxQueue:

    """1队列+1数组"""

    def __init__(self):

        self.queue = queue.Queue()

        self.stack = []      #  用于存放最大值的数组

    def max_value(self) -> int:

        return self.stack[0] if self.stack else -1

    def push_back(self, value: int) -> None:

        self.queue.put(value)     

        while self.stack and self.stack[-1] < value: #保持stack是递减的形式，并且该数值之前，都最大

            self.stack.pop()

        self.stack.append(value)

    def pop_front(self) -> int:

        if not self.stack: return -1 # stack为空，即对应的queue也为空了

        ans = self.queue.get()

        if ans == self.stack[0]:

            self.stack.pop(0)

        return ans

三、剑指 Offer 13. 机器人的运动范围

3.1 问题

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

   

示例 1：

输入：m = 2, n = 3, k = 1

输出：3

示例 2：

输入：m = 3, n = 1, k = 0

输出：1

3.2 代码

class Solution:

   

    def sum_rc(self,row,col):

        tmp = 0

        while row > 0:

            tmp += row % 10

            row //=  10

        while col > 0 :

            tmp += col % 10

            col //= 10

        return tmp

   

    def movingCount(self, m: int, n: int, k: int) -> int:

        marked = set()  # 将访问过的点添加到集合marked中,从(0,0)开始

        queue = collections.deque()

        queue.append((0,0))

        while queue:

            x, y = queue.popleft()

            if (x,y) not in marked and self.sum_rc(x,y) <= k:

                marked.add((x,y)) 

                for dx, dy in [(1,0),(0,1)]:  # 仅考虑向右和向下即可,注意在if内部

                    if 0 <= x + dx < m and 0 <= y + dy < n:

                        queue.append((x+dx,y+dy))  #增加两个坐标

        return len(marked)  

   

参考文献

【1】https://leetcode-cn.com/

【2】一题的答案动画解析

【3】第二题动画解析