题解 | #最小活动范围#

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;
        int[] minRanges = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }

            while (!deque.isEmpty() &&
                    nums[deque.peekLast()] >nums[i]) {
                deque.pollLast();
            }

            deque.offerLast(i);

            if (i >= k - 1) {
                minRanges[i - k + 1] = nums[deque.peekFirst()];
            }
        }

        return minRanges;
    }
}

知识点：

1. 动态规划
2. 栈
3. 队列