LeetCode每日1题--滑动窗口最大值

简介: LeetCode每日1题--滑动窗口最大值

前言


算法的重要性不言而喻!区分度高!

现在学习的门槛低了,只有能上网每个人都可以学编程!培训班6个月就可以培养出来能干活的人,你怎么从这些人中脱颖而出?没错!就是学算法,学一些底层和基础的东西。

说的功利点是为了竞争,卷死对手。真心话说就是能提高自己的基础能力,为技术可持续发展做好充分的准备!!!

提前入门学习书籍:CPrimerPlus、大话数据结构

image.png


刷题网站


代码随想录 (programmercarl.com)

leetcode

我是按照代码随想录提供的刷题顺序进行刷题的,大家也可以去刷leetcode最热200道,都可以

刷题嘛,最重要的就是坚持了!!!


画图软件


OneNote

这个要经常用,遇见不懂的流程的话就拿它画一画!


笔记软件


Typoral


题目


image.png


解析


思路

这种类型的题其实就是单调队列问题,但现在的问题是,没有现成的单调队列能给我们用,我们需要自己来建立一个单调队列

什么样的呢?


class MyQueue {
public:
    void pop(int value) {
    }
    void push(int value) {
    }
    int front() {
        return que.front();
    }
};

每次窗口移动的时候,调用pop(弹出元素),push(添加元素),front返回最大的值

我们这个窗口,没必要维护所有的元素,只要维护最大元素即可,然后保证队列是单调的即可。

自定义数组和弹出元素

  • 弹出元素时,比较当前要弹出的数值是否等于队列出口的数值,如果相等则弹出
  • 同时判断队列当前是否为空


Deque<Integer> deque = new LinkedList<>();
    void poll(int val) {
        if (!deque.isEmpty() && val == deque.peek()) {
            deque.poll();
        }
    }

添加元素

  • 添加元素的时候,添加元素大于入口元素,将入口元素弹出
  • 保证队列递增


void add(int val) {
        while (!deque.isEmpty() && val > deque.getLast()) {
            deque.removeLast();
        }
        deque.add(val);
    }

返回最大值


int peek() {
        return deque.peek();
    }

模拟滑动窗口

  • 建立数组存放结果
  • 调用自定义队列做单调队列
  • 返回结果数组
  • 根据题意:i为nums下标,是要在[i - k + 1, i]中选到最大值,只需要保证两点
  • 队列的头节点需要在[i - k + 1, i]范围内,不符合则要弹出


public int[] maxSlidingWindow(int[] nums, int k) {
  if (nums.length == 1) {
    return nums;
  }
  int len = nums.length - k + 1;
  int[] res = new int[len];
  int num = 0;
  MyQueue myQueue = new MyQueue();
  for (int i = 0; i < k; i++) {
    myQueue.add(nums[i]);
  }
  res[num++] = myQueue.peek();
  for (int i = k; i < nums.length; i++) {
    myQueue.poll(nums[i - k]);
    myQueue.add(nums[i]);
    res[num++] = myQueue.peek();
  }
  return res;
}

完整代码

完整代码如果还是看不懂可以去B站看一下视频讲解版的。


class MyQueue {
    Deque<Integer> deque = new LinkedList<>();
    void poll(int val) {
        if (!deque.isEmpty() && val == deque.peek()) {
            deque.poll();
        }
    }
    void add(int val) {
        while (!deque.isEmpty() && val > deque.getLast()) {
            deque.removeLast();
        }
        deque.add(val);
    }
    int peek() {
        return deque.peek();
    }
}
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        int n = nums.length;
        //存放结果集
        int[] res = new int[n - k + 1];
        int idx = 0;
        for(int i = 0;i<n;i++){
            while(!deque.isEmpty() && deque.peek() < i-k+1){
                // pop() 一般指弹栈 poll()指出队
                deque.poll();
            }
            //既然是单调,就要保证每次放进去的数字要比末尾的都大,否则也弹出
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]){
                deque.pollLast();
            }
            deque.offer(i);
            //因为单调,当i增长到符合第一个k范围的时候,每滑动一步都将该队列头节点放入结果就行了
            if(i >= k -1){
                res[idx++] = nums[deque.peek()];
            }
        }
        return res;
    }
}

相关文章
|
2月前
【LeetCode 26】239.滑动窗口最大值
【LeetCode 26】239.滑动窗口最大值
37 1
|
2月前
【LeetCode 04】滑动窗口法总结
【LeetCode 04】滑动窗口法总结
25 0
|
4月前
|
存储 Python
【Leetcode刷题Python】239. 滑动窗口最大值
文章介绍了两种解决LeetCode上"滑动窗口最大值"问题的方法:使用大堆树和双向递减队列,提供了详细的解析和Python代码实现。
37 0
|
6月前
|
算法 搜索推荐
力扣每日一题 6/15 滑动窗口
力扣每日一题 6/15 滑动窗口
37 1
|
6月前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
6月前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
5月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
6月前
|
算法 索引
力扣随机一题 位运算/滑动窗口/数组
力扣随机一题 位运算/滑动窗口/数组
48 0
|
6月前
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
|
6月前
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串