题解 | #最小活动范围#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @param k int整型
     * @return int整型一维数组
     */
    public int[] minSlidingWindow (int[] nums, int k) {
        // write code here

        //定义一个双端队列
        LinkedList<Integer> linkedList = new LinkedList<>();
        LinkedList<Integer> result = new LinkedList<>();
        int[] arr = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            while (linkedList.size() > 0 && nums[i] < nums[linkedList.peekLast()]) {
                linkedList.removeLast();
            }
            linkedList.addLast(i);
            if (i - linkedList.peekFirst() >= k) {
                linkedList.removeFirst();
            }
            if (i >= k - 1) {
                result.add(nums[linkedList.peekFirst()]);
            }

        }
        for (int i = 0; i < result.size(); i++) {
            arr[i] = result.get(i);
        }
        return arr;
    }

}

本题考察的知识点是单调队列的应用，所用编程语言是java。

我们应该知道单调队列是一种队列内的元素有单调性（单调递增或者单调递减）的队列，如果我们维持一个单调递增的队列，每次最优解就是队首元素，队尾则是最后进队的元素。但是如果维持一个单调递减的队列，在极端情况下第一个元素就是整个数组中的最小元素，那么队列中只会有第一个元素，然而这肯定是不符合题意的，题目要求在连续的k个小时内，牛的最小活动范围是多少，所以我们只能维持一个单调递增的队列。

我们通过判断队列头部和队列尾部的距离来判断是否需要将队列头部元素加入到集合中和移除队列头部元素。

移除队列头部元素在前，判断队列距离在后。因为判断是否需要将头部元素移除才能合适的将头部元素加入到集合中去。