题目描述

窗口滑动的每次其实就是踢出去一个前队友，加进来一个新队友的过程，我们第一次将前K个数作为首个滑动模板，
后面的每次滑动都是剔除模板的第一个数字，然后在最后加入一个新数字。
实现：用一个max变量记录目前窗口的最大值，而position来记录最大值的下标，当滑动时，每次用要新加入的数字与max比较。
求窗口头滑动到i时：
1.新加入数字：A（下标为i+k-1） 大于等于max，max变更为A，position变更为A的下标。
2.新加入数字：A （下标为i+k-1）小于max，判断position是否为i-1,不等于i-1则该窗口最大值依然为max，等于i-1时则需要重新对新窗口搜索最大值赋给max，并且记录position。

时间复杂度分析：最好情况下为O(n),最坏情况下为O(k(n-k))

C++ 代码

class Solution {
public:
vector[HTML_REMOVED] maxInWindows(vector[HTML_REMOVED]& nums, int k) {
vector[HTML_REMOVED] result;
int i = 0;
int max = nums[0];
int position = 0;
while(i<k)
{
if(max<=nums[i])
{
max = nums[i];
position = i;
}
i;
}
if(k == nums.size())
{
result.push_back(max);
return result;
}
result.push_back(max);//for first data
for(int i = 1;i<=nums.size()-k;i)
{
if(max<=nums[i+k-1])
{
max = nums[i+k-1];
position = i+k-1;
}
else{
if(position == i-1)
{
int j = i;
max = nums[i];
while(j<i+k)
{
if(max<=nums[j])
{
max = nums[j];
position = j;
}
j++;
}

            }
        }
         result.push_back(max);
    }
    return result;
}

};