最近主要看了RMQ算法的相关题目。这两天杂事比较多,所以看得进度比较慢。幸亏下周就没什么杂事啦,可以多学很多。
RMQ问题可以解决对于一个整数数组(也可以是其他可比较大小的元素类型)的任意区间[L, R]查询最值时,能在经过O(nlogn)的时间预处理后,做到O(1)时间复杂度的任意区间最大最小值查询。接下来大概写一下几种题目:
题目:给出一个非降序排列的整数数组a1,a2,...an,你的任务是对于一系列询问(i, j),回答ai,ai+1,...aj中出现最多次数的值所出现的次数?
思路:转化一下。把输入序列分成一段段由相同值构成的序列,然后对于每个查询[L,R]看他覆盖了哪些段,只要再这些连续的段范围内找出现次数的最大值即可,RMQ问题
题目思路:二维RMQ问题,求一个矩阵N*M中的一个小块矩阵内的最值问题.其中dmin[i][j][ii][jj]=x表示以(i , j)为左上角,以( i+(1<<ii)-1, j+(1<<jj)-1 )为右下角的矩阵内的最小值.dmax的值类似.把二维问题转变为一维问题来求解.
题目:在给定序列中求出一个区间,最小值是左边界,最大值是右边界。求最大区间长度。
思路:用RMQ存下最大值与最小值,然后枚举区间左边界,再用二分法找出满足“最小值是左边界”这个条件的最大区间的右边界编号,然后在这个区间里求出最大值,就是要求的区间了。