题解 | #滑动窗口的最大值#
滑动窗口的最大值
https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788
思路：最好不要直接对每个滑动窗口进行比较取最大值，不然容易造成超时
我们可以从下面几个方向考虑：
1.初始化：将第一个滑动窗口的最大值提取出来，然后放到结果中去，同时要维护一个最大值的位置的变量
2.遍历：随着滑动窗口的移动，可以有几种选择
1）如果最大值的位置仍处于这个滑动窗口期，那么此时滑动窗口最大值不变
2)如果此时最大值的位置小于窗口，当新加入的值大于前最大值，那么直接将最大位置的变量更新为新加入的值的位置
若是新加入的值小于前最大值，那么此时需要重新构建滑动窗口，然后拿出最大值即可，重复之前的步骤
class Solution {
private:
int temp_maxval = INT_MIN;
public:
vector<int> maxInWindows(const vector<int>& nums, int size) {
int iSize = nums.size();
vector<int> vec_res;
if(iSize < size)
{
//没理解，为什么这里就不对
const int i = *max_element(nums.begin(), nums.begin() + iSize);
vec_res.push_back(i);
return vec_res;
}
vector<int> vec_win;
vec_win.assign(nums.begin(), nums.begin() + size);
//temp_maxval = max(temp_maxval, *max_element(vec_win.begin(), vec_win.end()));
int max_position = max_element(vec_win.begin(), vec_win.end()) - vec_win.begin();
vec_res.push_back(nums[max_position]);
for(int i = size; i< iSize; i++)
{
//记录每次滑动窗口的最大值所在的位置
if(max_position >= i - size + 1 && nums[max_position] >= nums[i])
{
vec_res.push_back(nums[max_position]);
}
else if(max_position < i -size + 1&& nums[max_position] <= nums[i])
{
max_position = i;
vec_res.push_back(nums[max_position]);
}
else if(max_position >= i - size + 1 && nums[max_position] < nums[i])
{
max_position = i;
vec_res.push_back(nums[max_position]);
}
else{
vector<int> temp;
temp.assign(nums.begin() + i - size + 1, nums.begin() + i + 1);
//max_position代表的是当前的vec的指针位置，我们需要做的是还原即可
max_position = max_element(temp.begin(), temp.end()) - temp.begin() + i - size + 1;
vec_res.push_back(nums[max_position]);
}
}
return vec_res;
}
};