[数据结构与算法][亚麻高频题] Leetcode 239. Sliding Window Maximum(滑动窗口最大值)

题目描述 & 链接

Leetcode 239. Sliding Window Maximum:?定义一个窗口大小，求数组从头到尾窗口区域内最大值。

题目思路：

1. 单调栈

这道题目我们需要维护两个东西：一个是区域内最大值；另一个是如果窗口滑动导致当前最大值失效后，潜在的最大值。第一个区间最大值，可以直接以打擂台方式维护，但是潜在最大值我们则需要以大小顺序保存在后面。这里我们可以使用单调栈来进行维护。单调递增递减栈都可以，如果递减栈最大值保存在尾部，然后新加入的元素，根据单调递减关系保存在头部位置。

• 这里新元素加入头部，并非简单的直接加，而是会覆盖掉前面较小的元素
• 这里需要尾部和头部两端的信息，普通Stack无法实现，所以需要使用双边队列?Deque

为什么可以删除前面更小的元素，因为只要那些更小的元素和当前加入新元素在同一个窗口内，那些元素就对最大值没有贡献，而且这些更小的元素位置上又在新元素前面，滑动窗口时会被优先剔除，因此如果新的元素比之前这些元素大，可以直接将就得元素pop掉

注：这里单调栈除了要维护单调顺序外，还需要维护位置顺序，越新的元素在单调栈中位置越靠前

有了维护最大值方法，整道题目基本逻辑如下

Step 1. 建立双边队列作为单调栈
Step 2. 循环滑动窗口
Loop:
- 先看Stack内最大值是不是失效了 - 如果是 - pop
- 判断Stack内最大值和先加入元素大小关系 
    - 如果大 - 清空Stack(前面元素对后面最大值已无贡献)
    - 如果小 - 从头和栈中元素比较，清空比新元素小的旧元素
- 将新元素插入
- 更新当前窗口位置的最大值

根据上述思路，代码如下：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 栈顶维护最大值
        // 但是不是最大值的点也要保留，便于后续更新
        // 如果新加入元素比栈顶大，直接将所有元素清空 - 因为后续窗口滑动，最大值与其他元素无关
        // 如果新加入比栈顶小，清楚后面比当前元素小的元素
        // 需要双边队列进行单调栈维护
        Deque<Integer> stk = new ArrayDeque();
        int[] res = new int[nums.length-k+1];

        // init
        for(int i=0; i<k; i++) {
            if(!stk.isEmpty() && nums[i]>nums[stk.getLast()]) {
                stk.clear(); // 清空
            } else {
                while(!stk.isEmpty() && nums[i]>nums[stk.getFirst()]) {
                    stk.removeFirst(); // 递减栈前面小的删除掉
                }
            }
            stk.addFirst(i); //从头部找位置插入
        }

        res[0] = nums[stk.getLast()];

        for(int i=1; i<nums.length-k+1; i++) {
            if(stk.getLast()<i) stk.removeLast();
            if(!stk.isEmpty() && nums[i+k-1]>nums[stk.getLast()]) {
                stk.clear();
            } else {
                while(!stk.isEmpty() && nums[i+k-1]>nums[stk.getFirst()]) {
                    stk.removeFirst();
                }
            }
            stk.addFirst(i+k-1);
            res[i] = nums[stk.getLast()];
        }

        return res;
    }
}

时间复杂度：；空间复杂度：。?