剑指offer之滑动窗口的最大值

1 问题

给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值，列如，数组｛2,3,4,2,6,2,5,1｝的滑动窗口大小是3，一起6个滑动窗口，分别是{4，4，6，6，5}
 

2 分析

2,3,4,2,6,2,5,1
我们这里可以用双端队列，滑动窗口是3，我们先找出前3个数字里面的最大值，放在双端队列的头，然后依次向右滑动，确保每次滑动后队列的头是最大值。
 

3 代码实现

  

   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     

      #include <vector>
     
    
   

    

     

    
    

     

      #include <deque>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      vector<int> maxWindows(const vector<int> &nums, int size)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	vector<int> maxWindows;
     
    
   

    

     

    
    

     
	if (size <= 0 || nums.size() <= 0 || (nums.size() < size))
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		return maxWindows;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	deque<int> indexs;
     
    
   

    

     

    
    

     
	for (int i = 0; i < size; ++i)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		while (indexs.size() > 0 && nums[i] > nums[indexs.back()])
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			indexs.pop_back();
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      		indexs.push_back(i);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	for (int i = size; i < nums.size(); ++i)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		maxWindows.push_back(nums[indexs.front()]);
     
    
   

    

     

    
    

     
		while (indexs.size() > 0 && nums[i] > nums[indexs.back()])
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			indexs.pop_back();
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		while (indexs.size() > 0 && (i - indexs.front() >= size))
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			indexs.pop_front(); 
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      		indexs.push_back(i);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      	maxWindows.push_back(nums[indexs.front()]);
     
    
   

    

     

    
    

     
	return maxWindows;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	vector<int>  nums;
     
    
   

    

     

    
    

     

      	nums.push_back(2);
     
    
   

    

     

    
    

     

      	nums.push_back(3);
     
    
   

    

     

    
    

     

      	nums.push_back(4);
     
    
   

    

     

    
    

     

      	nums.push_back(2);
     
    
   

    

     

    
    

     

      	nums.push_back(6);
     
    
   

    

     

    
    

     

      	nums.push_back(5);
     
    
   

    

     

    
    

     

      	nums.push_back(2);
     
    
   

    

     

    
    

     

      	nums.push_back(1);
     
    
   

    

     

    
    

     
	vector<int>  result;
     
    
   

    

     

    
    

     

      	result = maxWindows(nums, 3);
     
    
   

    

     

    
    

     
	
     
    
   

    

     

    
    

     
	if (result.size() > 0)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		for (int i = 0; i < result.size(); ++i)
     
    
   

    

     

    
    

     
			std::cout << result[i] << std::endl;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

4 运行结果

  

   

    

     

    
    

     

      4
     
    
   

    

     

    
    

     

      4
     
    
   

    

     

    
    

     

      6
     
    
   

    

     

    
    

     

      6
     
    
   

    

     

    
    

     

      6
     
    
   

    

     

    
    

     

      5
     
    
  
 

5 总结

在一个数组里面，通过双端队列（qedue）求最大值

  

   

    

     

    
    

     
 std::deque<int> indexs;
     
    
   

    

     

    
    

     
 std::vector<int> nums;
     
    
   

    

     

    
    

     

       nums.push_back(1);
     
    
   

    

     

    
    

     

       nums.push_back(3);
     
    
   

    

     

    
    

     

       nums.push_back(2);
     
    
   

    

     

    
    

     

       nums.push_back(5);
     
    
   

    

     

    
    

     

       nums.push_back(4);
     
    
   

    

     

    
    

     
 for (int i = 0; i < nums.size(); ++i)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
		while (indexs.size() > 0 && nums[i] > nums[indexs.back()])
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			indexs.pop_back();
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      		indexs.push_back(i);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 std::cout << "maxValue is " << nums[indexs.front()] << std::endl;
     
    
  
 

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/98341186