剑指 Offer 59 - I. 滑动窗口的最大值

题目描述

给定一个数组nums和滑动窗口的大小k，请找出所有滑动窗口里的最大值。 
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
🔗题目链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof

思路

单调队列，维护一个队列使其队头元素为当前滑动窗口的最大值，具体操作如下：
  • 将进入窗口的新元素与队尾元素进行比较，新元素大于队尾元素就将队尾元素出队，否则就入队新元素，如窗口元素[1,3,-1]，则对应的队列元素为[3,,-1]；
  • 每次移动窗口时先判断移出窗口的元素，即窗口最左端的元素是否为队头元素，是就将其出队，再将新的元素入队到合适的位置，接着取队头元素存入结果数组，作为当前窗口的最大值。

🔗参考题解：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solution/mian-shi-ti-59-i-hua-dong-chuang-kou-de-zui-da-1-6/

代码实现 

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0 || k == 0){
            return new int[0];
        }
        int[] res = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        //维护队头元素为当前队列及滑动窗口中的最大值
        for(int i = 0; i < k; i++){ //先形成规定的滑动窗口
            while(!deque.isEmpty() && deque.peekLast() < nums[i]){
                //若当前元素大于队尾元素，就将队尾元素出队
                deque.removeLast();
            }
            deque.addLast(nums[i]); //将当前元素进行入队
        }
        res[0] = deque.peekFirst();
        for(int i = k; i < nums.length; i++){
            if(deque.peekFirst() == nums[i - k]){ 
                //若队头元素等于窗口最左端的值，即原窗口的最大值要被移出了，
                //则需要先将其出队，因为它已经不是本次窗口的最大值了
                deque.removeFirst();
            }
            //移除队列中小于窗口新元素的值，将新元素入队
            while(!deque.isEmpty() && deque.peekLast() < nums[i]){
                deque.removeLast();
            }
            deque.addLast(nums[i]);
            //取当前队列的队头元素加入结果数组
            res[i - k + 1] = deque.peekFirst();
        }
        return res;
    }
}

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

题目描述

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
🔗题目链接：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof

思路

单调队列，通过一个辅助队列维护队列的最大值，具体操作与上题类似。

代码实现 

class MaxQueue {

    Deque<Integer> deque;
    Deque<Integer> subDeque; //辅助队列
    public MaxQueue() {
        deque = new LinkedList<>();
        subDeque = new LinkedList<>();
    }
    
    public int max_value() {
        if(deque.isEmpty()){
            return -1;
        }
        return subDeque.peekFirst(); //返回队头元素
    }
    
    public void push_back(int value) {
        deque.offer(value);
        //将辅助队列中队尾元素与value比较，小于的移出队列，直到队列为空或遇到大于等于value的元素
        while(!subDeque.isEmpty() && subDeque.peekLast() < value){
            subDeque.removeLast();
        }
        subDeque.offer(value); //接着将该值入队
    }
    
    public int pop_front() {
        if(deque.isEmpty()){
            return -1;
        }
        int value = deque.poll();
        if(value == subDeque.peekFirst()){ //当出队元素与辅助队列队头元素相等时才出队
            subDeque.poll();
        }
        return value;
    }
}

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