Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

剑指 Offer 59 - II. 队列的最大值 #87

Open
Tcdian opened this issue Mar 26, 2020 · 1 comment
Open

剑指 Offer 59 - II. 队列的最大值 #87

Tcdian opened this issue Mar 26, 2020 · 1 comment
Labels

Comments

@Tcdian
Copy link
Owner

Tcdian commented Mar 26, 2020

剑指 Offer 59 - II. 队列的最大值

请定义一个队列并实现函数 max_value 得到队列里的最大值,要求函数max_valuepush_backpop_front 的均摊时间复杂度都是 O(1)

若队列为空,pop_frontmax_value 需要返回 -1

Example 1

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

Example 2

输入: 
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]

Note

  • 1 <= push_back,pop_front,max_value的总操作数 <= 10000
  • 1 <= value <= 10^5
@Tcdian
Copy link
Owner Author

Tcdian commented Mar 26, 2020

Solution

  • JavaScript Solution
var MaxQueue = function() {
    this.queue = [];
    this.max_queue = [];
};

/**
 * @return {number}
 */
MaxQueue.prototype.max_value = function() {
    if (this.queue.length > 0) {
        return this.max_queue[0];
    }
    return -1;
};

/** 
 * @param {number} value
 * @return {void}
 */
MaxQueue.prototype.push_back = function(value) {
    this.queue.push(value);
    if (this.max_queue.length > 0) {
        for (let i = this.max_queue.length - 1; i >= 0; i--) {
            if (this.max_queue[i] < value) {
                this.max_queue.pop();
            }
        }
    }
    this.max_queue.push(value);
};

/**
 * @return {number}
 */
MaxQueue.prototype.pop_front = function() {
    if (this.queue.length > 0) {
        const value = this.queue.shift();
        if (this.max_queue[0] === value) {
            this.max_queue.shift();
        }
        return value;
    }
    return -1;
};

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

@Tcdian Tcdian added the Design label May 3, 2020
@Tcdian Tcdian changed the title 《剑指 Offer(第 2 版)》59 - II. 队列的最大值 剑指 Offer 59 - II. 队列的最大值 Jun 30, 2020
@Tcdian Tcdian removed the Classic label Jul 30, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant