讨论/《画解剑指 Offer》 - 剑指 Offer 59 - I. 滑动窗口的最大值/
《画解剑指 Offer》 - 剑指 Offer 59 - I. 滑动窗口的最大值
共 2 个回复

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize){
if(numsSize == 0){
returnSize = 0;
return NULL;
}
int * stack = (int
) malloc(sizeof(int) * numsSize);
int * maxNums = (int*)malloc(sizeof(int) * (numsSize+1-k));
int top = 0;
int max;
int index = 0;
for(int i = numsSize -1; i >= 0; i--){
stack[top++] = nums[i];
}
while(index < (numsSize+1-k)){
max = stack[top-1];
for(int j = 0; j < k; j++){
if(stack[top - 1 -j] > max){
max = stack[top-1-j];
}
}
maxNums[index++] = max;
top--;
}
*returnSize = index;
return maxNums;
}

goby

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        queue = list()
        left = 1 - k
        right = 0
        res = []
        while(right < len(nums)):
            if left > 0 and queue[0] == nums[left - 1]:
                del queue[0]
            
            while queue and queue[-1] < nums[right]:
                del queue[-1]

            queue.append(nums[right])

            if left >= 0:
                res.append(queue[0])
            left += 1
            right += 1
        return res