题解 | #滑动窗口的最大值#

滑动窗口的最大值

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