class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
}
};
剑指 Offer 59 - I. 滑动窗口的最大值
给定一个数组 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/problems/sliding-window-maximum/
原站题解
javascript 解法, 执行用时: 264 ms, 内存消耗: 78.1 MB, 提交时间: 2022-11-30 23:40:25
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function(nums, k) {
const n = nums.length;
const prefixMax = new Array(n).fill(0);
const suffixMax = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
if (i % k === 0) {
prefixMax[i] = nums[i];
} else {
prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);
}
}
for (let i = n - 1; i >= 0; --i) {
if (i === n || (i + 1) % k === 0) {
suffixMax[i] = nums[i];
} else {
suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]);
}
}
const ans = [];
for (let i = 0; i < n - k + 1; i++) {
ans.push(Math.max(suffixMax[i], prefixMax[i + k - 1]));
}
return ans;
};
golang 解法, 执行用时: 184 ms, 内存消耗: 10 MB, 提交时间: 2022-11-30 23:40:10
func maxSlidingWindow(nums []int, k int) []int {
n := len(nums)
prefixMax := make([]int, n)
suffixMax := make([]int, n)
for i, v := range nums {
if i%k == 0 {
prefixMax[i] = v
} else {
prefixMax[i] = max(prefixMax[i-1], v)
}
}
for i := n - 1; i >= 0; i-- {
if i == n-1 || (i+1)%k == 0 {
suffixMax[i] = nums[i]
} else {
suffixMax[i] = max(suffixMax[i+1], nums[i])
}
}
ans := make([]int, n-k+1)
for i := range ans {
ans[i] = max(suffixMax[i], prefixMax[i+k-1])
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
python3 解法, 执行用时: 680 ms, 内存消耗: 27.6 MB, 提交时间: 2022-11-30 23:39:56
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
prefixMax, suffixMax = [0] * n, [0] * n
for i in range(n):
if i % k == 0:
prefixMax[i] = nums[i]
else:
prefixMax[i] = max(prefixMax[i - 1], nums[i])
for i in range(n - 1, -1, -1):
if i == n - 1 or (i + 1) % k == 0:
suffixMax[i] = nums[i]
else:
suffixMax[i] = max(suffixMax[i + 1], nums[i])
ans = [max(suffixMax[i], prefixMax[i + k - 1]) for i in range(n - k + 1)]
return ans
python3 解法, 执行用时: 316 ms, 内存消耗: 27.8 MB, 提交时间: 2022-11-30 23:39:46
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
q = collections.deque()
for i in range(k):
while q and nums[i] >= nums[q[-1]]:
q.pop()
q.append(i)
ans = [nums[q[0]]]
for i in range(k, n):
while q and nums[i] >= nums[q[-1]]:
q.pop()
q.append(i)
while q[0] <= i - k:
q.popleft()
ans.append(nums[q[0]])
return ans
golang 解法, 执行用时: 184 ms, 内存消耗: 9.9 MB, 提交时间: 2022-11-30 23:39:33
func maxSlidingWindow(nums []int, k int) []int {
q := []int{}
push := func(i int) {
for len(q) > 0 && nums[i] >= nums[q[len(q)-1]] {
q = q[:len(q)-1]
}
q = append(q, i)
}
for i := 0; i < k; i++ {
push(i)
}
n := len(nums)
ans := make([]int, 1, n-k+1)
ans[0] = nums[q[0]]
for i := k; i < n; i++ {
push(i)
for q[0] <= i-k {
q = q[1:]
}
ans = append(ans, nums[q[0]])
}
return ans
}
javascript 解法, 执行用时: 376 ms, 内存消耗: 77.7 MB, 提交时间: 2022-11-30 23:39:18
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function(nums, k) {
const n = nums.length;
const q = [];
for (let i = 0; i < k; i++) {
while (q.length && nums[i] >= nums[q[q.length - 1]]) {
q.pop();
}
q.push(i);
}
const ans = [nums[q[0]]];
for (let i = k; i < n; i++) {
while (q.length && nums[i] >= nums[q[q.length - 1]]) {
q.pop();
}
q.push(i);
while (q[0] <= i - k) {
q.shift();
}
ans.push(nums[q[0]]);
}
return ans;
};
java 解法, 执行用时: 99 ms, 内存消耗: 58.2 MB, 提交时间: 2022-11-30 23:39:02
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] pair1, int[] pair2) {
return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
}
});
for (int i = 0; i < k; ++i) {
pq.offer(new int[]{nums[i], i});
}
int[] ans = new int[n - k + 1];
ans[0] = pq.peek()[0];
for (int i = k; i < n; ++i) {
pq.offer(new int[]{nums[i], i});
while (pq.peek()[1] <= i - k) {
pq.poll();
}
ans[i - k + 1] = pq.peek()[0];
}
return ans;
}
}
golang 解法, 执行用时: 236 ms, 内存消耗: 9.6 MB, 提交时间: 2022-11-30 23:38:43
var a []int
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return a[h.IntSlice[i]] > a[h.IntSlice[j]] }
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{} { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }
func maxSlidingWindow(nums []int, k int) []int {
a = nums
q := &hp{make([]int, k)}
for i := 0; i < k; i++ {
q.IntSlice[i] = i
}
heap.Init(q)
n := len(nums)
ans := make([]int, 1, n-k+1)
ans[0] = nums[q.IntSlice[0]]
for i := k; i < n; i++ {
heap.Push(q, i)
for q.IntSlice[0] <= i-k {
heap.Pop(q)
}
ans = append(ans, nums[q.IntSlice[0]])
}
return ans
}
python3 解法, 执行用时: 576 ms, 内存消耗: 39.7 MB, 提交时间: 2022-11-30 23:38:20
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
# 注意 Python 默认的优先队列是小根堆
q = [(-nums[i], i) for i in range(k)]
heapq.heapify(q)
ans = [-q[0][0]]
for i in range(k, n):
heapq.heappush(q, (-nums[i], i))
while q[0][1] <= i - k:
heapq.heappop(q)
ans.append(-q[0][0])
return ans