【剑指offer59】队列的最大值

• 题目辨析：这里的操作pop_front和push_back就是常规双向队列的意义，就是按照先进先出的规则来进行，唯一要做的是，需要实时最新队列的最大元素；

• 解题技巧：
  解题技巧维护一个双向队列，使得队首元素始终是目前队列的最大元素

• code

class MaxQueue {
public:
    deque<int> que;
    deque<int> que_M;
    MaxQueue() {

    }
    
    int max_value() {
        if(que.empty())
            return -1;
        return que_M.front();
    }
    
    void push_back(int value) {
        que.push_back(value);
        while(que_M.size()>0 && que_M.back()<value)
            que_M.pop_back();
        que_M.push_back(value);
        return;
    }
    int pop_front() {
        if(que.empty())
            return -1;
        int temp = que.front();
        if(temp == que_M.front())
            que_M.pop_front();
        que.pop_front();
        return temp;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

• 延申
  维护双向队列的最大元素这个技巧在求滑动数组的最大值的时候运用的淋漓尽致

• code

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> que;
        vector<int> res;
        if(nums.size()==1)
            return {nums[0]};
        if(nums.size()<=k)
            return {nums[distance(nums.begin(), max_element(nums.begin(),nums.end()))]};
        for(int i=0;i<k;i++)
        {      
            while(!que.empty() && que.back() < nums[i])
                que.pop_back();
            que.push_back(nums[i]);
        }
        res.push_back(que.front());
        for(int i=k;i<nums.size();i++)
        {
            if(que.front()==nums[i-k])
                que.pop_front();

            while(!que.empty() && que.back() < nums[i])
                que.pop_back();
            que.push_back(nums[i]);
            res.push_back(que.front());
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29