Return the max sliding window-CodePudding

You are given an array of integers nums and a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. You have to compute the maximum inside the window.

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;
        
    }
};

But throws an error

=================================================================
==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

CodePudding user response：

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

Say k is 3, and n is 2. When i = 1, j will go to 3. nums[3] is then out-of-bounds. You need to carefully review j=1 and j<i k. Both are wrong.

Also, int mx = nums[i]; is more elegant and doesn't involve special constants like INT_MIN.

CodePudding user response：

Using the deque did the trick

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;
}