返回最大滑动窗口

Question

您将得到一个整数数组、num数组和一个大小为k的滑动窗口，该窗口正从数组的最左边移动到非常右侧。你只能看到窗口中的k个数字。每次滑动窗口以一个位置向右移动。你必须计算窗口内的最大值。

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k) {
        int n=nums.size();
        vector<int> answer;
        for(int i=0; i<n; i++){
            int mx = INT_MIN;
            for(int j=1; j<i+k; j++){
                mx = max(mx, nums[j]);
            }
            answer.push_back(mx);
        }
        while(answer.size()>n-k+1){
            answer.pop_back();
        }
        return answer;
        
    }
};

但是抛出一个错误

=================================================================
==31==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x603000000090 at pc 0x000000345e1e bp 0x7ffef610bff0 sp 0x7ffef610bfe8
READ of size 4 at 0x603000000090 thread T0
    #2 0x7fb1bb36d0b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
0x603000000090 is located 0 bytes to the right of 32-byte region [0x603000000070,0x603000000090)
allocated by thread T0 here:
    #6 0x7fb1bb36d0b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
Shadow bytes around the buggy address:
  0x0c067fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c067fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c067fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c067fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c067fff8000: fa fa 00 00 00 07 fa fa fd fd fd fa fa fa 00 00
=>0x0c067fff8010: 00 00[fa]fa 00 00 00 00 fa fa fa fa fa fa fa fa
  0x0c067fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==31==ABORTING

Answer 1

    for(int i=0; i<n; i++){
        int mx = INT_MIN;
        for(int j=1; j<i+k; j++){
            mx = max(mx, nums[j]);

假设k为3，n为2，当i =1时，j将变为3，nums[3]为禁区。您需要仔细检查j=1和j<i+k。两者都错了。

而且，int mx = nums[i];更优雅，不涉及像INT_MIN这样的特殊常量。

Answer 2

用德克做了个小把戏

vector<int> maxSlidingWindow(vector<int> &nums, int k) {
    int n = nums.size();
    deque<int> dq(k);
    vector<int> answer;
    for (int i = 0; i < k; i++) {
        while (dq.size() && nums[i] >= nums[dq.back()]) {
            dq.pop_back(); 
        }
        dq.push_back(i);
    }
    for (int i = k; i < n; i++){
        answer.push_back(nums[dq.front()]);
        while(dq.size() && dq.front() <= i - k) {
            dq.pop_front();
        } 
        while(dq.size() && nums[i] >= nums[dq.back()]) {
            dq.pop_back();
        }
        dq.push_back(i);
    }
    answer.push_back(nums[dq.front()]);
    return answer;
}