劍指offer之滑動(dòng)窗口的最大值

1 問(wèn)題

給定一個(gè)數(shù)組和滑動(dòng)窗口的大小，請(qǐng)找出所有滑動(dòng)窗口里的最大值，列如，數(shù)組｛2,3,4,2,6,2,5,1｝的滑動(dòng)窗口大小是3，一起6個(gè)滑動(dòng)窗口，分別是{4，4，6，6，5}
 
2 分析

2,3,4,2,6,2,5,1
我們這里可以用雙端隊(duì)列，滑動(dòng)窗口是3，我們先找出前3個(gè)數(shù)字里面的最大值，放在雙端隊(duì)列的頭，然后依次向右滑動(dòng)，確保每次滑動(dòng)后隊(duì)列的頭是最大值。
 

 
3 代碼實(shí)現(xiàn)

    #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 運(yùn)行結(jié)果

    4
    4
    6
    6
    6
    5

 
5 總結(jié)

在一個(gè)數(shù)組里面，通過(guò)雙端隊(duì)列（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;



 


作者：chen.yu
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號(hào)：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)