滑动窗口的最大值 (leetcode 239)

一：解题思路

方法一：使用二层循环进行遍历。O(k*n)

方法二:

方法三：

二：完整代码示例 (C、C++、Java、Python)

方法一C:

int max(int a, int b)
{
    return a > b ? a : b;
}

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) 
{
    if (numsSize == 0) return nums;
    int* result = (int*)malloc(sizeof(int)*(numsSize-k+1));
    int left = 0;
    int maxValue = 0;
    int i = 0;
    for (left = 0; left <= numsSize - k; left++)
    {
        maxValue = nums[left];
        for (i = left; i < left + k; i++)
        {
            maxValue = max(maxValue,nums[i]);
        }
        result[left] = maxValue;
    }

    *returnSize = numsSize - k + 1;

    return result;
}

方法二C:

方法三C:

方法一C++:

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) 
    {
        if (nums.size() == 0) return nums;
        int n = nums.size();
        vector<int> result(n-k+1,0);
        for (int left = 0; left <= n - k; left++)
        {
            int maxValue = nums[left];
            for (int i = left; i < left + k; i++)
            {
                maxValue = max(maxValue,nums[i]);
            }
            result[left] = maxValue;
        }

        return result;
    }
};

方法二C++:

方法三C++:

 方法四C++(利用双端队列来做):

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if (nums.size() == 0) return nums;
        deque<int> window;
        deque<int> result;

        for (int i = 0; i < nums.size(); i++) {
            if ((i >= k) && (window[0] <= i - k))
                window.pop_front();
            while (!window.empty() && nums[window[window.size() - 1]] <= nums[i])
            {
                window.pop_back();
            }
            window.push_back(i);
            if (i >= k - 1)
                result.push_back(nums[window[0]]);
        }

        vector<int> ret;

        while (!result.empty()) {
            ret.push_back(result.front());
            result.pop_front();
        }

        return ret;
    }
};

方法一Java:

方法二Java:

方法三Java:

方法一Python:

方法二Python(双端队列的方法):

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums:
            return []
        window,result=[],[]#window存放下标，result存放最后的数组结果
        for i,x in enumerate(nums):
            if i>=k and window[0]<=i-k:
                window.pop(0)
            while window and nums[window[-1]]<=x:
                window.pop()
            window.append(i)
            if i>=k-1:
                result.append(nums[window[0]])
        return result