前言
算法的重要性不言而喻！区分度高！
现在学习的门槛低了，只有能上网每个人都可以学编程！培训班6个月就可以培养出来能干活的人，你怎么从这些人中脱颖而出？没错！就是学算法，学一些底层和基础的东西。
说的功利点是为了竞争，卷死对手。真心话说就是能提高自己的基础能力，为技术可持续发展做好充分的准备！！！
提前入门学习书籍：CPrimerPlus、大话数据结构
刷题网站
我是按照代码随想录提供的刷题顺序进行刷题的，大家也可以去刷leetcode最热200道，都可以
刷题嘛，最重要的就是坚持了！！！
画图软件
OneNote
这个要经常用，遇见不懂的流程的话就拿它画一画！
笔记软件
Typoral
题目
解析
思路
这种类型的题其实就是单调队列问题，但现在的问题是，没有现成的单调队列能给我们用，我们需要自己来建立一个单调队列
什么样的呢？
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; } }
