21 | 队列与单调队列：滑动区间最大值

老师，我目前在北京某985读书，平时实验室做得机器学习，大部分代码就是简单得把矩阵运算翻译成matlab和python，但感觉除了matlab其他得编程语言都写得很业余，想来是自己非科班不够努力，同时其他语言对计算得封装是不如matlab完善的。但应该什么样的训练方法可以快速提高呢？本科偏数学，毕业后想去大厂面试（机器学习&深度学习）算法岗，大概还有5年的硕博学习时间，除了数学上的持续学习，（计算机科班培养计划这边学习了geek的深入理解计算机原理，在啃推荐的那本《深入理解计算机系统》,也在和这门课同时学习geek的数据结构与算法之美，看懂容易，自己上手就有点难度了，基本上跟着抄一边）计算机科班的东西我应该主要补一下哪些内容呢?有什么好的学习路径的推荐和学习建议吗？希望老师能指点一下，万分感谢！

老师不好意思，我知道我代码出错的概率大很多很多： 输入：nums = [1,3,-1,-3,5,3,6,7], n = 8, m = 3 错误输出：[3, 3, 5, 3, 6, 7] 正确输出：[3, 3, 5, 5, 6, 7] 第四项不知道为啥错了，是copy您的代码然后输出的，不知道是不是您的代码哪里写错了。当然，更大可能是我的代码写错了（笑哭）。看了两个多小时了呀，都看不懂这段代码，我是不是太钻牛角尖了（笑哭）。 https://github.com/HappyJoo/CLearningScript/blob/master/Heap/239_Sliding_window_maximum.cpp

老师好，我还是没理解单调数列里单调性的概念，比如老师给的例程，q数组里应该存储的是滑动窗口中a数组最大值对应的序号值，以6 4 2] 10 3 8 5 9，应该是0，3，5，7（序号），那么q里这个数组单调性体现在哪儿呢？只能是滑动窗口值是单调的。理解力不好，谢谢老师

老师讲的算法用数学语言去理解感觉讲的太到位了，很好理解，但是再去转换成机器思维好像就不知道如何表达了……听了老师今天的课感觉在入门编程之前应该先再去学学入门前的入门课，比如数据结构，基础算法，组成原理，微积分、离散数学等等；感觉真是正如高德纳大师——冯诺依曼之后最伟大的计算机科学家说的如果连《计算机程序设计艺术》的卷一都学不懂干脆就别当程序员了。另外高德纳大师说的“只要不是对计算机只有一时兴趣的人，都应该学好机器语言，这是计算机的基础。”这个说法正对上了和胡光老师说的“学习编程，与其说是将我们的思维转换成代码，不如说是将我们的思维，锻炼成计算机的思维。”胡老师和高德纳老师的这个训练机器思维如出一辙呀！那么问题来了，如和才能用正确的姿势学好那天书一样的机器语言呢？

老师你好啊~我现在不知道要看啥，c专家与编程好像还早了点，课程其他内容虽然还没有完全消化，但是也差不多了，有点不知道应该干什么，去leetcode刷题吗？还是看一些例如C与指针，啃一下大部头？还是去看看《数据结构与算法之美》，或者《深入了解计算机原理》，或者《编译原理之美》？又或者去看看python？有点不知道要走哪个方向，迷茫~

茶艺师学编程 1、“数据结构，就是定义一种结构，并且维护这个结构。”这句话值得好好品味。 2、初看老师的给的代码，我是蒙的，为什么不是直接的a[n]而是要a[q[n]]，后来才回过神来，例子中的的q[n]是坐标轴，区间滑动就是在它上面进行的，a[q[n]]才这个轴的值。这里可以打个比方，就是我要到某青年旅馆找我的朋友a[q[n]]，朋友给了我他的房间号（q[n])。我比对了n个房间号，终于找到q[n]房号，这才敲门进屋，看见我的朋友a[q[n]]，而不是没每到一个房间前就踹门而进看看里面是什么人。 文中例子的完整可行代码如下： #include <stdio.h> #define MAX_N 1000 int q[MAX_N + 5], head, tail; void interval_max_number(int *a, int n, int m){ head = tail = 0; for (int i = 0; i < n; i++){ while (head < tail && a[q[tail - 1]] < a[i])tail--; q[tail++] = i; if (i - m == q[head])head++; if(i + 1 >= m){ printf("interval(%d, %d)", i - m + 1, i); printf(" = %d\n", a[q[head]]); } } return ; } int main(){ int a[8] = {6, 4, 2, 10, 3, 8, 5, 9}; int n = 8; int m = 3; interval_max_number(a, n, m); return 0 ; }

在这个最大值单调队列维护的过程中有2个点： 1、元素在区间最大； 2、元素是否已经过期。 最开始直接在单调队列存数值本身，结果发现判断过期还需要额外的空间 后面反应过来来用索引既能获得数值也能判断过期 这个是我在思维上的一个槛，不知道啥时候才能自然跨过这个问题