【一天三道算法题】代码随想录——Day15（困难题只有一道）

这篇具有很好参考价值的文章主要介绍了【一天三道算法题】代码随想录——Day15（困难题只有一道）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一. 滑动窗口最大值

题目链接：力扣

思路：

这道题我认为最难的是编程语言本身并没有一个可以让你完全直接开始使用的一个数据结构，也就是说要自己造轮子。并且为了尽可能的减少维护元素的个数我们要学会去在能实现功能的前提下，维护尽可能少的数组元素。

但是，Java为什么是神？我们可以利用Java中的双端队列来实现这一点！这会让我们的操作减少很多，减少了我们做题的负担。

代码：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        ArrayDeque<Integer> que = new ArrayDeque<>();
        int n = nums.length;
        //结果数组，用于存放最终的结果，而n-k+1则是作为滑动窗口的大小，实现移动
        int[] result = new int[n-k+1];
        int index = 0;
        for(int i=0; i<n; i++) {
            //根据题意，i为nums下标，要在nums[n-k+1, i]中选出最大值，只需保证两点
            //1.队列头结点需要在[i-k+1, i]范围内，不符合要弹出
            while(!que.isEmpty() && que.peek() < i-k+1) {
                que.poll();
            }
            //2.因为是单调，要保证每次放进去的数字都比末尾的大，否则弹出
            while(!que.isEmpty() && nums[que.peekLast()] < nums[i]) {
                que.pollLast();
            }
            //3.将i添加进队列中
            que.offer(i);

            //因为单调，当i增长到符合第一个k范围时，每滑动一步就将队列头结点放入队列即可
            if(i>=k-1) {
                result[index++] = nums[que.peek()];
            }
        }
        return result;
    }
}

人生中第一道困难题，确实有难度，需要反复理解。

今天只有一道题，我要把它吃透。文章来源地址https://www.toymoban.com/news/detail-613788.html

到了这里，关于【一天三道算法题】代码随想录——Day15（困难题只有一道）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！