2021-04-02算法打卡

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

若队列为空，pop_front 和 max_value 需要返回 -1

示例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]

var MaxQueue = function() {
    this.queue = []
    this.maxVal = -1

};

/**
 * @return {number}
 */
MaxQueue.prototype.max_value = function() {
    return this.maxVal
};

/** 
 * @param {number} value
 * @return {void}
 */
MaxQueue.prototype.push_back = function(value) {
    this.queue.push(value)
    if (value > this.maxVal) {
        this.maxVal = value
    }
};

/**
 * @return {number}
 */
MaxQueue.prototype.pop_front = function() {
    let item = this.queue.shift() || -1
    if (this.queue.length === 0) {
        this.maxVal = -1
    } else {
        this.maxVal = Math.max(...this.queue)
    }
    return item
};

/**
 * 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()
 */

2、滑动窗口最大的值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    if(nums.length === 0) return []
    let resultArr = []
    let i = 0
    while(i + k < nums.length) {
        let tempArr = nums.slice(i, i+k)
        resultArr.push(Math.max(...tempArr))
        ++i
    }
    let itemArray = nums.slice(i)
    resultArr.push(Math.max(...itemArray))
    console.log(resultArr,'resultArr')
    return resultArr
};