NO64、滑动窗口的最大值(经典，越到最后越经典)

64、滑动窗口的最大值

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
窗口大于数组长度的时候，返回空
示例1
输入

[2,3,4,2,6,2,5,1],3

返回值

[4,4,6,6,6,5]

1、自己想的，边界条件很多

总的来说，利用 low high maxIndex三个指针维护整个数组的情况

1、滑动窗口大小为0，num数组为空，滑动窗口大于 num.size 也不符合规矩，直接返回空

2、先考虑第一个滑动窗口的情况，走一遍，找出最大值的index

 vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
    vector<int> result;
    if (num.size() == 0 || size == 0 || size > num.size()) return result;
    if (size == num.size()) {
        result.push_back(*max_element(num.begin(), num.end())); 
         return result;
      }

    int low = 0, high = size - 1, maxIndex = 0;
    int len = num.size();
    for (int i = 0; i <= high; ++i) {
        if (num[i] > num[maxIndex])  maxIndex = i;
    }
    //result.push_back(num[maxIndex]); //这里不能直接先push，要不然第一个滑动窗口的最大值会push两次
    while (high <= len - 1) {
        if (maxIndex == low - 1) {//如果maxIndex还是上个窗口的最低索引，需要更新
            maxIndex = low;
            for (int i = low; i <= high; ++i)
                if (num[i] > num[maxIndex])  maxIndex = i;

        }
        else if (num[maxIndex] < num[high]) //如果最新添加进来的high索引比原窗口中的所有值都要大，也要更新
        {
            maxIndex = high;
        }
        high++;
        low++;

        result.push_back(num[maxIndex]);

    }
    return result;
    }

2、第二种做法，比较水，借助优先队列来做，大顶堆

vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
    vector<int> result;
    if (num.size() == 0 || size == 0 || size > num.size()) return result;
    priority_queue<int> pri_que;
    int count = 0;
    for (int