题解 | #最小活动范围#

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. 队列

解题思路：

使用了一个双端队列（deque）来维护一个滑动窗口，窗口的大小为k。我们从数组的开头开始遍历，对于每个位置，我们首先检查队首元素是否在当前窗口内，如果不在，则将其从队首移除。然后，我们将当前位置的元素依次与队尾元素比较，如果队尾元素大于当前元素，则将其从队尾移除，以保持队列中的元素递增。然后，将当前位置加入队尾。当窗口的大小达到k时，我们将队首元素（即窗口内的最小元素）加入结果数组中。