本文共 1006 字，大约阅读时间需要 3 分钟。
问题A：
数组上滑动窗口的最大值：双端队列，时间O(N)
维护一个左端存放当前窗口最大值的双端队列， 从左到右元素只能满足降序，否则将最小元素弹出。其中，双端队列只存放下标。
例如，2，3，4，2，6，2，5，1
步骤： 2 -> 3 -> 4 -> 4,2 -> 4,6 -> 6,2 -> 6,5 -> 5,1 其中，从第三个正式进入窗口，最大值为4，4，4，6，6，5问题B：
最大值减最小值<=给定值的子数组数量：维护两个双端队列，maxq和minq，保存当前窗口最大值和最小值。时间O(N)
窗口滑动，当满足情况时，R++，不满足时，L++，当L==R时，R++，直到边界。
问题C：
需要排序的最短子数组长度：左向右遍历，记录左侧最大值，找到最大值最终的位置R。
右向左遍历，记录右侧最小值，找到最小值最终的位置L。 则[L,R]即为最短距离。问题D：
子矩阵的最大累加和：dp，时间O(NNN)
最外层循环size，含义为计算必须高度为size的子矩阵累加和
中层循环行起始i，则i+size则为循环选定的子矩阵 最内层循环列起始j，则(i+size)*j 则是选定子矩阵。通过维护纵向窗口累加和+求解数组横向最大累加和，得到最大值。
问题E：
数组中为出现的最小正整数：思维题+窗口缩小，时间O(N)
因为数组长度为N，则解一定是1～N+1，则只需要判断1～N是否有即可。
窗口缩小，L=0，R=N-1;
[L,R]不仅即代表解区间，也代表下标，通过交换元素Arr[L++]和Arr[R–]来缩小[L,R]区间以及解空间。当Arr[L]正好等于L+1，说明L+1一定不是解，解空间减小为[L+1,R]。
当Arr[L]的值小于L或大约R，或者和Arr[Arr[L]-1]重复，则代表这个数与解无关，并且解空间会减少，则和最后元素交换 ，R–。 以上情况都没出现，则交换Arr[L]和Arr[Arr[L]-1]。直到解区间缩小为L >= R，返回L+1。
问题F：
数组排序后相邻数最大差值：排序方法，时间O(N*logN)
排序方法有很多比较是冗余的，利用桶排序思想，时间降为O(N)
取最大数max和最小数min，将区间划分为（max - min）/ N 个，max独占N+1桶，每个桶只记录最大值和最小值。
由于数组长度为N，桶个数为N+1，则最大差一定位于不同当桶。
转载地址：http://nbwji.baihongyu.com/