题解 | #最小活动范围#

知识点

单调队列

解题思路

维护一个队列来保存下标，队列的头部存放最小值。

进入循环，如果头部的下标等于i - k，表示已经出了k的范围，移出队列

再把队列尾部大于等于nums[i]的数全部移出，那么对列中如果有值，头部的第一个就是k范围内的最小值；如果队列为空，最小值就是当前的nums[i]。

Java题解

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param k int整型 
     * @return int整型一维数组
     */
    public int[] minSlidingWindow (int[] nums, int k) {
        // write code here
        int n = nums.length;
        Deque<Integer> deque = new ArrayDeque<>();
        int[] ans = new int[n - k + 1];
        for(int i = 0; i < n; i++){
            if(!deque.isEmpty() && deque.peekLast() == i - k) deque.pollLast();
            while(!deque.isEmpty() && nums[i] <= nums[deque.peekFirst()]){
                deque.pollFirst();
            }
            if(i >= k - 1){
                ans[i - k + 1] = deque.isEmpty() ? nums[i] : nums[deque.peekLast()];
            }
            deque.offerFirst(i);
        }
        return ans;
    }
}