返回最大滑动窗口

Question

给定一个整数nums数组和一个大小为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

使用deque达到了效果

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