讨论/《图解算法数据结构》 - 剑指 Offer 59 - I. 滑动窗口的最大值/
《图解算法数据结构》 - 剑指 Offer 59 - I. 滑动窗口的最大值
共 32 个回复

"你可以假设 k 总是有效的,在输入数组不为空的情况下,1 ≤ k ≤ 输入数组的大小。"
测试样例:[] 0
官方,做不到要不咱就别多这一嘴

16

TypeScript ===

function maxSlidingWindow(nums: number[], k: number): number[] {
    if (nums.length === 0) return nums // 输入数组要不为空

    let subArr: number[] = []
    let index: number = 0

    while (index + k <= nums.length) {
        let max: number = nums[index]

        for (let i=index; i<index+k; i++) {
            if (nums[i] > max) max = nums[i]
        }

        subArr.push(max)
        index ++
    }

    return subArr
};
2
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 如果数组为空
        if(nums.length <= 0){
            return new int[]{};
        }

        // 创建返回数组
        int a[] = new int[nums.length - k + 1];
        // 先找出第一组中最小的
        int max = 0;
        for(int i = 0; i < k; i++){
            if(nums[max] < nums[i]){
                max = i;
            }
        }
        a[0] = nums[max];
        // 遍历num,依次找出每个组中最大的
        for(int i = k; i < nums.length; i++){
            // 如果最大的下标没有在当前组中,遍历新数组找到最大的下标
            if(max <= i - k){
                max = i - k + 1;
                for(int j = max + 1; j <= i; j++){
                    if(nums[max] < nums[j]){
                        max = j;
                    }
                }
            } else if(nums[max] < nums[i]){ // 最大的在新的组中,和新加入组中的比较,获得最大下标
                max = i;
            }
            a[i - k + 1] = nums[max];
        }
        return a;
    }
}
2

直接return{};

2

##切片,暴力

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        len1 = len(nums) - k + 1
        res = []
        for i in range(len1):
            cur: List = nums[i: i + k]
            if cur:
                res.append(max(cur))

        return res
1

笑死我了

1

本人拙劣的JS写法:
var maxSlidingWindow = function(nums, k) {
let priorMaxVal = nums[0];
let priorMaxIndex = 0;
let result = [];
let i = 0;
while(i<nums.length){
if(priorMaxVal<nums[i]){
priorMaxVal = nums[i];
priorMaxIndex = i;
}else if(priorMaxIndex <= i - k){
//当前最小值滑出,重新计算
priorMaxIndex = i - k + 1;
priorMaxVal = nums[i - k + 1];
for(let j = i - k + 2;j<=i;j++){
if(priorMaxVal<nums[j]){
priorMaxVal = nums[j];
priorMaxIndex = j;
}
}
}
if(i>=k-1)result.push(priorMaxVal);
i++;

}
return result;

};

1
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q, res = [], []
        for i, num in enumerate(nums):
            while q and num > nums[q[-1]]: q.pop()
            q.append(i)
            if i - k + 1 > q[0]: q.pop(0)
            if i >= k - 1: res.append(nums[q[0]])
        return res
1

捕获.PNG

不说话了看图!

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

比较好想的python解法