🌕 239. 滑动窗口最大值

难度: 🌕

问题描述

---

解法

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 思路：
        // 借助 双端队列 - 非严格递减
        // 每次遇到比栈顶小于等于的元素压栈，遇到大于的一直弹栈
        // 最大值永远在栈底
        LinkedList<Integer> stack = new LinkedList<>();
        // 第一遍遍历填充初始栈
        for(int i = 0; i < k; i ++) {
            if(stack.isEmpty()) {
                stack.push(nums[i]);
            } else {
                int cur = nums[i];
                int peek = stack.peekLast();
                if(cur <= peek) {
                    stack.addLast(cur);
                } else {
                    // 弹栈，知道满足条件
                    while(!stack.isEmpty() && stack.peekLast() < cur) {
                        stack.removeLast();
                    }
                    stack.addLast(cur);
                }
            }
        }
        int len = nums.length;
        int[] res = new int[len - k + 1];
        res[0] = stack.peekFirst();
        int index = 1;
        // 之后每次只移动一位
        for(int i = k; i < len; i ++) {
            // test(stack);
            // 此时栈肯定不为空，判断右移一位导致删除的元素是否是栈顶元素
            int cur = nums[i];
            int peek = stack.peekFirst();
            int rv = nums[i - k];
            if(peek == rv) {
                stack.removeFirst();
            }
            // 此时就不一定栈是否为空了
            if(stack.isEmpty()) {
                stack.push(cur);
            } else {
                if(cur <= stack.peekLast()) {
                    stack.addLast(cur);
                } else {
                    while(!stack.isEmpty() && cur > stack.peekLast()) {
                        stack.removeLast();
                    }
                    stack.addLast(cur);
                }
            }
            res[index] = stack.peekFirst();
            index ++;
        }
        return res;
    }

    private void test(LinkedList<Integer> list) {
        int len = list.size();
        System.out.println(" -----");
        for(int i = 0; i < len; i ++) {
            System.out.print(list.get(i) + "  ");
        }
    }
}

---

输出