面试题59:队列的最大值

题目

滑动窗口的最大值
给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，它们的最大值分别为{4,4,6,6,6,5},如下表所示

image.png

解题思路

1. 定义一个deque的数据容器名为index用来存放滑动窗口最大值的数组下标。
2. 定义一个vector的数据容器名为maxInWindows存放符合条件的最大值
3. 名为index的两端开口的队列，在存入一个数字的下标之前，要先判断队列里已有数字是否小于待存入的数字。如果已有数字小于带存入数字，那么这些数字不可能是滑动窗口的最大值，因此会被依次从队列的尾部删除
4. 若队列头部的数据已经滑出窗口，应把该数字从队列的头部删除

代码

• 细节

1. 保证我们的子函数是有效的，数组的长度大于滑动窗口的长度，并保证滑动窗口的长度大于1
2. 第一个for循环是找第一个滑动窗口中最大值的下标
3. 第二个for循环中，开始移动滑动窗口。注意点一保证滑动窗口中的下标对应的数字是最大的，注意点二保证滑动窗口中的下标是有效的，即时刻判断滑动窗口中最大值下标与当前处理数字的下标之差小于滑动窗口的大小

class Solution{
  public:
    vector<int> maxInWindows(const vector<int>& num,unsigned int size)
    {
        vector<int> maxInWindows;
        //保证数组中的数字大小大于滑动窗口大小
        if(num.size() >= size && size >= 1)
        {
            deque<int> index;
            for(unsigned int i = 0;i<size;++i)
            {   //index.back()指的是返回容器最后一个数据
                while(!index.empty() && num[i] >= num[index.back()])
                {
                    index.pop_back();//删除容器中最后一个数据
                } //把比容器中数据大的数组数字下标加进去
                index.push_back(i);
                
            }
            //size=3是滑动窗口的大小，num.size()是数组的大小
            for(unsigned int i = size;i<num.size();++i)
            {   //把deque容器中存储的第一个下标对应的元素加入maxInWindows
                //cout << num[index.front()] << endl;
                maxInWindows.push_back(num[index.front()]);
                //若有数组元素大于deque容器中的元素，则删除容器中的元素
                while(!index.empty() && num[i]>= num[index.back()])
                {
                    index.pop_back();
                }
                //若头部元素超过滑动窗口，删除
                if(!index.empty() && index.front() <= (int)(i-size) )
                {
                    index.pop_front();
                }
                index.push_back(i);
                //cout << i << endl;
            }
            maxInWindows.push_back(num[index.front()]);
        }
        return maxInWindows;
    }
};

完整代码见Github