【Leetcode笔记】滑动窗口最大值

Leetcode原题链接：滑动窗口最大值

一、思路

1、暴力

• 窗口滑动一次，提一个最大值出来，时间复杂度巨高O(n*k)，自然没通过- -

2、优秀思路

• 一个思考的盲区：总想维护滑动框内的所有值，实际没必要，只需要保证每次滑动弹出的是最大值即可，因此采用以下思路。
• 自制一个双向单调队列，进行一定规则的pop、push、getMaxValue操作。
• ①pop操作：这里有个误解，我本来以为是无脑弹出队列头部，其实每次弹出的是滑动框的第一个元素num[i]，因此在pop操作中实际上是要比较当前队列头是否等于num[i]，若等于，才弹出，否则虽然调用了函数，其实什么也没做。采取这种pop方式可以在循环num[i]的时候，既保证了滑动框后移一位，又不会误删队列头那个元素。（补充：如果新数在在数值上等于队列头，但位置上不等，那也把队列头弹出，这时虽然的确“误删”了队列头元素，但实际上删掉的那个数值还在队列中，仍可以维护队列头最大的情况，还不明白可以看下面的例子。）
• ②push操作：每次push进来一个新数前，先循环判断新数是否大于队尾，若大于，把原队尾pop掉，删除所有比新数小的数后，再将新数push进来，这样就完好的维护了单调队列。
• ③getMaxValue操作：其实就是获取队列头元素。

思虑再三感觉还是举个例子好理解：
比如现在队列是[3,1,2]的情况，下一个循环到的数字是3，现在进入循环，
主函数会先进行pop操作，此时由于新数和队列头相等，队列头pop掉，变为[1,2]，
（虽然此时队列不是单调队列了，但实际上主函数的本次循环并没有结束，只需要保证在每次循环后单调即可）
然后主函数进行push操作，由于新数3比队列数字都大，经过push操作后，队列就变为了[3]，结束循环。

可见，经过一次循环即滑动框的一次移动，队列仍然保持单调递减
1
2
3
4
5
6
7

二、代码

from collections import deque


class MyQueue: #单调队列（从大到小
    def __init__(self):
        self.queue = deque() #这里需要使用deque实现单调队列，直接使用list会超时
    
    #每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
    #同时pop之前判断队列当前是否为空。
    def pop(self, value):
        if self.queue and value == self.queue[0]:
            self.queue.popleft()#list.pop()时间复杂度为O(n),这里需要使用collections.deque()
            
    #如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
    #这样就保持了队列里的数值是单调从大到小的了。
    def push(self, value):
        while self.queue and value > self.queue[-1]:
            self.queue.pop()
        self.queue.append(value)
        
    #查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
    def front(self):
        return self.queue[0]
    
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        que = MyQueue()
        result = []
        for i in range(k): #先将前k的元素放进队列
            que.push(nums[i])
        result.append(que.front()) #result 记录前k的元素的最大值
        for i in range(k, len(nums)):
            que.pop(nums[i - k]) #滑动窗口移除最前面元素
            que.push(nums[i]) #滑动窗口前加入最后面的元素
            result.append(que.front()) #记录对应的最大值
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

三、总结

• 太难了，总结经验的话，实在是需要思维跳出题目的框框，毕竟第一感觉都是维护整个滑动框的内容，看完解析后发现其实也不用，维护“最大值”就行了。不过还是记住这道题比较好，实在很难想到。
• 除了暴力算法外其实也尝试了分情况讨论，尝试了半天还是失败了，下面贴上试错过程代码，本来想每次维护“最大”和“次大”两个元素，结果维护一轮发现维护了个寂寞。

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ret = []
        last_max_pos = 0  # 上一组滑动框最大数字的位置
        last_big_pos = 0  # 上一组滑动框次大数字的位置
        # 最大次大不会同位置，后面会体现
        start_pos = 0  # 滑动框第一个数字位置
        end_pos = k - 1  # 滑动框最后一个数字位置

        # 开始循环
        for i in range(len(nums)):
            big = nums[i+k-1]  # 初始化，每次纳入一个新数，先假定它最大
            # 情况一：若k=1
            if k == 1:
                return nums
            # 情况二：k!=1，第一组滑动框至少先比出一个最大的
            if i == 0:
                for j in range(k-1):
                    if nums[j] > nums[j+1]:
                        big = nums[j]
                        last_max_pos = j
                        last_big_pos = j+1
                    else:
                        big = nums[j+1]
                        last_max_pos = j+1
                        last_big_pos = j
                ret.append(big)
                # 第一个滑动框最大值提取完成，滑到下一组，调整几个参数
                start_pos += 1
                end_pos += 1
                # 这时，看滑动框超出去没，没超出去就继续，超出去了直接break
                if end_pos <= len(nums)-1:
                    continue
                else:
                    break
            # 情况三：现在得到了第一组框里最大的数和次大的数的位置
            # 首先，上一组最大的位置在不在这一组内
            if last_max_pos >= start_pos:  # 如果在，拿新数和它比较即可
                if nums[end_pos] >= nums[last_max_pos]:  # 如果新数更大，直接加进去，更新最大数位置
                    ret.append(nums[end_pos])
                    last_max_pos = end_pos
                else:  # 如果老数更大，也直接加进去
                    ret.append(nums[last_max_pos])
                # 无论如何，更新新框位置
                start_pos += 1
                end_pos += 1
                continue
            else:  # 如果不在，那次大肯定在，拿新数和它比较即可，无论如何，次大要不然变成了最大，要不然还是次大
                if nums[end_pos] >= nums[last_big_pos]:  # 如果新数更大，直接加进去，次大仍为次大
                    ret.append(nums[end_pos])
                    last_max_pos = end_pos
                else:  # 如果次大更大，直接加进去，次大变为最大，次大没了，操
                    ret.append(nums[last_big_pos])
                    last_max_pos = last_big_pos
                # 无论如何，更新新框位置
                start_pos += 1
                end_pos += 1
                continue

# 想太久了，想不出来了，放弃，看解析TAT   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

部分内容参考代码随想录