【leetcode】19. 栈&队列-队列的最大值

发表于 更新于 分类于 阅读次数： 本文字数： 1.7k 阅读时长 ≈ 2 分钟

题目

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
难易程度:Medium

示例 1：

输入:
[“MaxQueue”,”push_back”,”push_back”,”max_value”,”pop_front”,”max_value”]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

示例 2：

输入:
[“MaxQueue”,”pop_front”,”max_value”]
[[],[],[]]
输出: [null,-1,-1]
 
限制：
1 <= push_back,pop_front,max_value的总操作数 <= 10000
1 <= value <= 10^5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

分析

本题和包含min函数的栈有点类似，但是要复杂很多。因为栈是在列表的异端操作，在push和pop操作时能够决定当前栈的最大值最小值。而队列pop和back操作是在列表的两端操作，因此队列在不同状态下的最值是变动的。

设有队列：[8,3,5,4,1,2]
则最大值队列：[8,5,4,2]

1
2
3
4
5
6
i = 0; max = 8; [8]
i = 1; max = 5; [8,5]
i = 2; max = 5; [8,5]
i = 3; max = 4; [8,5,4]
i = 4; max = 2; [8,5,4,2]
i = 5; max = 2; [8,5,4,2]

假设上述队列中加入新元素9,则最大值对列：[9]
也即，队列中每个位置i的对应最大值max是索引区间[i, n]之间的最大值，因此，最大值队列是一个单调递减队列。因此，当有元素入队列的时候，需要逆序遍历更新最大值队列。

说明：1 <= value <= 10^5也算是常数时间了和队列长度，操作次数无关。

时间复杂度：O(1)
空间复杂度：O(1)

代码

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
32
33
34
35
36
37
38
39
40
41
42
43
44
class MaxQueue {
    queue<int> q;
    deque<int> max;
public:
    MaxQueue() {
        q = queue<int>();
        max = deque<int>();
    }
    
    int max_value() {
        if (max.empty()) {
            return -1;
        }
        return max.front();
    }
    
    void push_back(int value) {
        while (!max.empty() && value > max.back()) {
            max.pop_back();
        }
        max.push_back(value);
        q.push(value);
    }
    
    int pop_front() {
        if (q.empty()) {
            return  -1;
        }
        int res = q.front();
        q.pop();
        if (res == max.front()) {
            max.pop_front();
        }
        return res;
    }
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */