欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCodeEasy-【面试题58 - II. 左旋转字符串】

程序员文章站 2022-04-30 22:06:55
...

给定一个数组 nums 和滑动窗口的大小 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

提示:
你可以假设 k 总是有效的,在输入数组不为空的情况下,1 ≤ k ≤ 输入数组的大小。

注意:本题与主站 239 题相同:https://leetcode-cn.com/problems/sliding-window-maximum/
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路1:暴力

直接遍历每个窗口,找到最大值,稍微优化的可以记录当前窗口的最大值,然后滑动到下一个窗口时判断出局的数是不是最大的,如果是则需要重新找最大值,如果不是则只需要在最大值和新加入窗口的值中进行判断即可。
LeetCodeEasy-【面试题58 - II. 左旋转字符串】

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if nums == []:
            return []
        i, j = 0, k - 1
        max_num = -0x3f3f3f3f
        ans = []
        for l in range(k):
            if l < len(nums) and max_num < nums[l]:
                max_num = nums[l]
        ans.append(max_num)
        while i + k < len(nums):
            if nums[i] < max_num:
                if nums[j+1] > max_num:
                    max_num = nums[j+1]
            else:
                max_num = -0x3f3f3f3f
                for l in range(i+1, j+2):
                    if max_num < nums[l]:
                        max_num = nums[l]
            ans.append(max_num)
            i += 1
            j += 1
        return ans

思路2:单调队列

LeetCodeEasy-【面试题58 - II. 左旋转字符串】
LeetCodeEasy-【面试题58 - II. 左旋转字符串】

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):
            if i >= len(nums):
                break
            while deque and deque[-1] < nums[i]: # 保持(非严格)单调递减
                deque.pop()
            deque.append(nums[i])
        ans = [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.pop()
            deque.append(nums[i])
            ans.append(deque[0])
        return ans