力扣 hot100 滑动窗口最大值 单调双端队列 java 简单题解

题目链接239. 滑动窗口最大值 - 力扣LeetCode题目描述给你一个整数数组nums有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。示例 1输入nums [1,3,-1,-3,5,3,6,7], k 3输出[3,3,5,5,6,7]解释滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 731 [3 -1 -3] 5 3 6 731 3 [-1 -3 5] 3 6 751 3 -1 [-3 5 3] 6 751 3 -1 -3 [5 3 6] 761 3 -1 -3 5 [3 6 7]7示例 2输入nums [1], k 1输出[1]提示1 nums.length 105-104 nums[i] 1041 k nums.length我的思路创建一个队列然后在遍历数组的过程中对比队尾和最新的数用while遍历并且判断队尾小就不抛弃大的话就抛弃后面添加最新的i的数据判断队头是否小于等于i-k来确定当前的最大值是否不存在于窗口来绝对抛弃实现窗口的更新最后让一个答案数组记录当前队头的数值也就是答案我的代码class Solution { public int[] maxSlidingWindow(int[] nums, int k) { LinkedListInteger integers new LinkedList(); for (int i 0; i k; i) { while (!integers.isEmpty()nums[i]nums[integers.peekLast()]){ integers.pollLast(); } integers.offerLast(i); } int[] ints new int[nums.length - k 1]; ints[0] nums[integers.peekFirst()]; for (int i k; i nums.length; i) { while (!integers.isEmpty()nums[i]nums[integers.peekLast()]){ integers.pollLast(); } integers.offerLast(i); while (integers.peekFirst()i-k){ integers.pollFirst(); } ints[i-k1]nums[integers.peekFirst()]; } return ints; } }