上海大学校赛K迷宫
迷宫
https://ac.nowcoder.com/acm/contest/5278/K
第一眼：bfs傻X题，然后发现它能跳。
然后嘴巴BB了一句，起点bfs，终点bfs，单调栈+单调栈合并的傻X题。
好吧，这个题确实是没什么可以说的地方，没思路的话可能是不知道“单调队列处理固定划窗极值”这个套路。
还是给个例子比较好说明，假设n=9,k=3，a[]={5,6,7,8,9,4,1,1,1}
跟着划窗取子区间，取到的第一个子区间是{5,6,7}这个子区间，该子区间的最大值为7。
那么想一个问题，5和6两个数字有没有可能在划窗向右滑动的过程中作为一个最大值？
你发现是不可能的，因为5和6比7要小，并且他们的物理位置在7的左侧，划窗向右滑动的过程中5和6比7更早的被弹出这个划窗区间。
那既然没必要保留，那我存都不带存的，也就是对于{5,6,7}这个子区间有用的信息只有7。
那么在向右滑动1步之后7,8之间也是由于相同的原因，7再也不可能在8之后成为任何一个子区间的极值。
那么一直向右滑动划窗，直到{8,9,4}这段区间。虽然9是当前划窗内的极值，但是4这个备胎是有可能上位的。因为它寿命比9要长，等9被弹出划窗的时候它还在里面，所以4是要被保留的。
那么总结一下就是维护一个数据结构，每当输入的数据比tail位置的数字大时，就弹出最末尾的数字，反之只要单调递减就压进去。
所以维护一个“单调递减队列”就能够维护固定长度的划窗最大值问题。
跟这个题有什么关系呢，使用单调队列的话可以很轻松的扩展到k维空间。
对于这个题，其实就是起点bfs，终点bfs，然后找一个矩形区域内的最小值。
首先先把矩阵一行一行的切开，也就是把它变成“n个长度为m的一维数组”
然后就求出了“所有长度是定长的线段的极值”。
然后在对列在做一次，这次的权值改为刚刚每行线段求出的极值，再来一遍。
就变成了二维固定形状的矩阵的极值。
这种方法的复杂度仅为O(|高维空间容量|)，而且实现起来也比ST表要简单，内存使用也比ST表更优。
然后嘴巴BB了一句，起点bfs，终点bfs，单调栈+单调栈合并的傻X题。
（...几小时后...）
MD这个题怎么这么麻烦。好吧，这个题确实是没什么可以说的地方，没思路的话可能是不知道“单调队列处理固定划窗极值”这个套路。
单调队列处理固定划窗极值
它是这么个套路啊，说现在有一个长度大小为n的数组，数组中有一些整数，请你求出所有长度大小为k的子区间的极值。还是给个例子比较好说明，假设n=9,k=3，a[]={5,6,7,8,9,4,1,1,1}
跟着划窗取子区间，取到的第一个子区间是{5,6,7}这个子区间，该子区间的最大值为7。
那么想一个问题，5和6两个数字有没有可能在划窗向右滑动的过程中作为一个最大值？
你发现是不可能的，因为5和6比7要小，并且他们的物理位置在7的左侧，划窗向右滑动的过程中5和6比7更早的被弹出这个划窗区间。
那既然没必要保留，那我存都不带存的，也就是对于{5,6,7}这个子区间有用的信息只有7。
那么在向右滑动1步之后7,8之间也是由于相同的原因，7再也不可能在8之后成为任何一个子区间的极值。
那么一直向右滑动划窗，直到{8,9,4}这段区间。虽然9是当前划窗内的极值，但是4这个备胎是有可能上位的。因为它寿命比9要长，等9被弹出划窗的时候它还在里面，所以4是要被保留的。
那么总结一下就是维护一个数据结构，每当输入的数据比tail位置的数字大时，就弹出最末尾的数字，反之只要单调递减就压进去。
所以维护一个“单调递减队列”就能够维护固定长度的划窗最大值问题。
跟这个题有什么关系呢，使用单调队列的话可以很轻松的扩展到k维空间。
对于这个题，其实就是起点bfs，终点bfs，然后找一个矩形区域内的最小值。
首先先把矩阵一行一行的切开，也就是把它变成“n个长度为m的一维数组”
然后就求出了“所有长度是定长的线段的极值”。
然后在对列在做一次，这次的权值改为刚刚每行线段求出的极值，再来一遍。
就变成了二维固定形状的矩阵的极值。
这种方法的复杂度仅为O(|高维空间容量|)，而且实现起来也比ST表要简单，内存使用也比ST表更优。
虾皮信息成长空间 249人发布