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.
暴力法
这个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.
双向队列
不得不说，这次官方题解比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.
光头大神解法：
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.
动态规划
划分数组，然后用两个数组，存从左向右，和从右向左的最大值。
然后一次遍历，去两头最大值
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.
