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

#include <cstddef>
#include <vector>

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型vector 
     * @param size int整型 
     * @return int整型vector
     */
    vector<int> maxInWindows(vector<int>& num, int size) {
        // write code here
        std::vector<int> maxNumList;
        std::vector<int> storedNode;
        if (num.size() < size or size == 0){
            return maxNumList;
        }
        if (num.size() == 1 or size == 1){
            return num;
        }
        for (int start_pivot = 0; start_pivot <= num.size()-size; start_pivot++){
            std::vector<int> window(size);
            std::copy(num.begin()+start_pivot, num.begin()+start_pivot+size, window.begin());
            if (start_pivot == 0){
                int max = window[0];
                storedNode = initStoredNode(window, max);
                maxNumList.push_back(max);
            }else{
                maxNumList.push_back(findMaxInList(storedNode, window));
            }
        }
        return maxNumList;
    }

    vector<int> initStoredNode(vector<int>& window, int& max){
        vector<int> storedNode;
        for (int i = 0; i < window.size(); i++){
            if (max < window[i]){
                max = window[i];
            }
            if (i < window.size()-1 and window[i] >= window[i+1] and i != 0){
                storedNode.push_back(window[i]);
            }
        }
        storedNode.push_back(window[window.size()-1]);
        return storedNode;
    }

    int findMaxInList(vector<int>& storedNode, vector<int>& window){
        int max = window[window.size()-1];
        for (auto &elem : storedNode){
           if (elem >= max){
                max = elem;
           }
        }
        if (storedNode[0] == window[0]){
            storedNode.erase(storedNode.begin());
        }
        if (storedNode[storedNode.size()-1] < window[window.size()-1]){
            storedNode.erase(storedNode.end()-1);
        }
        storedNode.push_back(window[window.size()-1]);

        return max;
    }
};