剑指offer 滑动窗口的最大值

拼搏现实的明天。 2022-06-08 05:55 162阅读 0赞

# 1、题目 #

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

# 2、分析 #

用双端队列存放滑动窗口可能的最大值的下标。注意：是下标，因为需要判断元素是否被移出了窗口。  
移动窗口时：  
1）若最大值被移出窗口，需要**删除最大值**  
2）若新加入的元素**比队尾的元素大**，则比该元素小的其他元素不可能成为最大值，依次**移除**这些元素，把**新元素加入队列**  
3）若新加入的元素**比队尾的元素小**，该元素也有可能会成为最大值，**把它加入队列**

# 3、代码 #

void maxOfWindow(vector<int> nums, int k) {
        vector<int> window;
        if (nums.size() > k&&k >= 1) {
            deque<int> index;
            for (int i = 0; i < k; i++) {
       //第一个滑动窗口
                while (!index.empty() && nums[index.back()] <= nums[i])
                    index.pop_back();//最大元素下标
                index.push_back(i);
            }
            for (int i = k; i < nums.size(); i++) {
                window.push_back(nums[index.front()]);//队首保存最大元素下标
                while (!index.empty() && nums[index.back()] <= nums[i])
                    index.pop_back();
                if (!index.empty() && index.front() <= i - k)
                    index.pop_front();
                index.push_back(i);
            }
            window.push_back(nums[index.front()]);
        }
        for(int x:window)
            cout<<x<<"　"; 
        cout << endl;
    }