190 - 239 滑动窗口最大值

题目

给定一个数组 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

提示：

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

进阶：

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

解答

想到的方法是，用一个变量存当前最大值，然后for循环遍历push进答案里面

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums:
            return []
        iterate = len(nums)-k+1
        m = max(nums[:k])
        ans = [m]
        for i in range(1, iterate):
            if nums[k+i-1] > m:
                m = nums[k+i-1]
            elif m == nums[i-1]:
                m = max(nums[i:i+k])
            ans.append(m)
        return ans

Runtime: 156 ms, faster than 93.11% of Python3 online submissions for Sliding Window Maximum.

Memory Usage: 19.5 MB, less than 88.46% of Python3 online submissions for Sliding Window Maximum.

居然真的成功了

刷了190题之后，有生之年，不看题解破了一道困难题

可把我激动坏了

可喜可贺、可喜可贺

哈哈哈哈哈我简直太帅了

而且仔细一看效率还不错吼

哈哈哈哈

go版本！

func arrMax(arr []int) int {
    m := arr[0]
    for _, v := range arr {
        if v > m {
            m = v
        }
    }
    return m
}
func maxSlidingWindow(nums []int, k int) []int {
    if len(nums) == 0 {
        return []int{}
    }
    iterate := len(nums) - k + 1
    max := arrMax(nums[:k])
    ans := []int{max}
    for i := 1; i < iterate; i++ {
        if nums[k+i-1] > max {
            max = nums[k+i-1]
        } else if max == nums[i-1] {
            max = arrMax(nums[i : i+k])
        }
        ans = append(ans, max)
    }
    return ans
}

Runtime: 820 ms, faster than 73.52% of Go online submissions for Sliding Window Maximum.

Memory Usage: 8.6 MB, less than 100.00% of Go online submissions for Sliding Window Maximum.

不知道为啥那么慢

var maxSlidingWindow = function(nums, k) {
  if (nums.length == 0) {
    return []
  }
  const iterate = nums.length - k + 1
  let max = Math.max(...nums.slice(0, k))
  let ans = [max]
  for (let i = 1; i < iterate; i++) {
    if (nums[k + i - 1] > max) {
      max = nums[k + i - 1]
    } else if (max === nums[i - 1]) {
      max = Math.max(...nums.slice(i, i + k))
    }
    ans.push(max)
  }
  return ans
};

Runtime: 96 ms, faster than 58.20% of JavaScript online submissions for Sliding Window Maximum.

Memory Usage: 41.4 MB, less than 100.00% of JavaScript online submissions for Sliding Window Maximum.

暴力法

https://leetcode-cn.com/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetcode-3/

这个python版本好简洁。。

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        if n * k == 0:
            return []
        return [max(nums[i:i+k]) for i in range(n-k+1)]

Runtime: 704 ms, faster than 20.95% of Python3 online submissions for Sliding Window Maximum.

Memory Usage: 19.3 MB, less than 96.15% of Python3 online submissions for Sliding Window Maximum.

双向队列

https://leetcode-cn.com/problems/sliding-window-maximum/solution/dan-diao-dui-lie-by-labuladong/

不得不说，这次官方题解比lab大佬说得清楚😏

简言之，双向队列。两边都能push和pop。底层用链表就能实现。

插入的时候，把小于自己的元素都删掉。相当于在插入过程中就过滤了一遍小的。

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        from collections import deque
        if len(nums) == 0 or k == 0:
            return []
        if k == 1:
            return nums
        n = len(nums)

        def clean_deque(i):
            if deq and deq[0] == i-k:
                deq.popleft()
            while deq and nums[i] > nums[deq[-1]]:
                deq.pop()

        deq = deque()
        max_idx = 0
        for i in range(k):
            clean_deque(i)
            deq.append(i)
            if nums[i] > nums[max_idx]:
                max_idx = i

        output = [nums[max_idx]]

        for i in range(k, n):
            clean_deque(i)
            deq.append(i)
            output.append(nums[deq[0]])
        return output

Runtime: 192 ms, faster than 43.50% of Python3 online submissions for Sliding Window Maximum.

Memory Usage: 19.4 MB, less than 88.46% of Python3 online submissions for Sliding Window Maximum.

光头大神解法：

https://leetcode.com/problems/sliding-window-maximum/discuss/65901/9-lines-Ruby-11-lines-Python-O(n)

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        from collections import deque
        d = deque()
        out = []
        for i, n in enumerate(nums):
            while d and nums[d[-1]] < n:
                d.pop()
            d += [i]
            if d[0] == i-k:
                d.popleft()
            if i >= k-1:
                out += [nums[d[0]]]
        return out

Runtime: 168 ms, faster than 75.46% of Python3 online submissions for Sliding Window Maximum.

Memory Usage: 19.4 MB, less than 88.46% of Python3 online submissions for Sliding Window Maximum.

动态规划

划分数组，然后用两个数组，存从左向右，和从右向左的最大值。

然后一次遍历，去两头最大值

image.png

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if len(nums) == 0 or k == 0:
            return []
        if k == 1:
            return nums
        n = len(nums)

        left = nums.copy()
        right = nums.copy()
        for i in range(1, n):
            if i % k != 0:
                left[i] = max(left[i-1], nums[i])
            j = n-i-1
            if (j+1) % k != 0:
                right[j] = max(right[j+1], nums[j])
        out = []
        for i in range(n-k+1):
            out.append(max(left[i+k-1], right[i]))
        return out

Runtime: 192 ms, faster than 37.86% of Python3 online submissions for Sliding Window Maximum.

Memory Usage: 19.5 MB, less than 88.46% of Python3 online submissions for Sliding Window Maximum.