1.概述
这篇blog来源于leetcode。加入了第198场周赛，后果比前几次周赛惨很多。不过没关系，及时发现了本人很菜，路漫漫其修远兮！这边blog次要是针对周赛第四题衍收回来的思考。次要包含RMQ问题以及本人思考题目标过程。价值不是很大，轻易写写。
2.RMQ问题
RMQ（Range Minimum / Maximum Query ）次要是用来求区间最值问题钻研进去的算法。
对于RMQ问题有很多办法能够求解，比方线段树，或者应用动静布局。对于动态区间的RMQ问题，应用DP是十分好了解的。上面咱们就来聊聊。
举个简略的例子
比方给定一个无序数组arr。求数组所有区间的最值。如果通过暴力枚举，必定会TLE。然而咱们很容易想到。对于一个大的区间[0,1]，咱们能够将其分为两个子区间:[0,1]和[2,3]。那么大区间的最值，其实能够通过两个子区间失去。
应用动静布局的思维
大问题的后果依赖若干个子问题。
既然应用动静布局，咱们就须要列出状态转移方程。
咱们令dpi示意：以第i个数为终点，间断2^j个数 的区间最值。比方dp2就是区间[2,3]的最值。3怎么来。其实就是2+2^1-1 ，减1时减掉第一个数。
接下来咱们考虑一下边界条件（对于动静布局，边界条件是解决问题的突破口）
根据下面定义：dpi代表数组第i个数开始，间断一个数的区间的最值。间断一个数，其实就只有一个，就是他自身。
所以咱们失去,这里咱们假如数组arr 是从1开始。
dp[i][0]=arr[i];推导转移方程
对于dpi，咱们如何做求值？
其实能够将这个区间分为2局部。第一部分为dpi，第二局部为dpi+(1<<(j-1))。而后依赖两个区间的后果再求大区间的最值。
大家看到这两个区间可能很懵逼。不焦急看，咱们一个一个来剖析。
- 首先是dpi，这个区间咱们应该很容易了解。就是以i开始，共2^(j-1)个数。其实就是以i开始，2^j的前半部分。因为2^(j-1)是2^j的一半。
- 其次是dpi+(1<<(j-1))。这个看起来简单。但从上可知，这个示意的就是残余半个区间的最值。咱们依据dp的定义来推到一下。后半局部区间就是从前半个区间最初一个元素的后一个元素到区间开端。那么咱们就须要计算一下后半个区间的开始地位。其实就是大区间初始地位i+区间长度的一半。长度计算依赖j。所以就能够失去是i+(1<<(j-1))。
这里的思维就是一分为2。前提是分进去的区间的后果是提前晓得的。
所以咱们能够失去状态转移方程(以区间最大值举例)：
dp[i][j]= max {dp[i][j-1],dp[i+(1<<(j-1)][j-1]} 查问最值
通过下面过程，咱们将最值计算出来，然而咱们如何获取后果呢？
咱们假如len为要查问区间的长度。咱们log(len)也就是咱们dpi中j的长度。然而咱们并不能保障2^log(len)==len。因为len不肯定是2的整数幂。所以咱们并不能保障区间的完整性。
如果该长度正好是2的幂。那么没故障，后果为dpi，否则咱们会脱漏一些区间，如下图。那么如何解决问题呢？
大家能够看到咱们能够应用dpi和dpr-(1<<k)+1。应用后者是为了补充咱们的脱漏。然而大家可能会放心有反复。然而如果是求最值问题，反复是不会影响后果的。所以，很ok。
3.较量题目剖析
题目链接：
https://leetcode-cn.com/probl...
题目剖析：
咱们对函数剖析后，发现对于l<=r，他的后果是一个递加的序列。因为与运算。与的越多最终值越小。如果一个区间[l,r]按上述函数进行与。后果必定小于等于区间最小值。
既然是一个有序序列，咱们就能够应用二分。咱们枚举右边界。而后通过二分对区间求值并记录后果。工夫简单为nlog(n)
没错，开始我就是这么做的，然而：
看到这个，我就开始定位耗时。应该是在进行区间与运算的时候浪费时间。
所以咱们须要进行优化。
于是我想到了区间最值问题。与运算其实和其是一样的。比方同一个大的区间的与运算后果，咱们能够通过两个小区间的后果再进行与操作。
并且对于反复与雷同数字，后果是不会受影响的，这个比拟要害，因为咱们在查问区间最值的时候，会反复计算。
于是我用动静布局构建区间后果。最终解决了问题。
贴出代码
RMQ动静布局代码实现
//RMQ问题代码type RMQ struct { Dp [][]int}func (rmq *RMQ) init(arr []int) { dp := make([][]int, len(arr)) rmq.Dp = dp for i := 0; i < len(arr); i++ { dp[i] = make([]int, 20) } //初始化条件。从i起的一个数（2^0）的最小值 就是该数。 for i := 1; i < len(arr); i++ { dp[i][0] = arr[i] } // for j := 1; (1 << j) < len(arr); j++ { for i := 1; i+(1<<(j-1)) < len(arr); i++ { //这里须要留神 为什么临界条件为i+(1<<(j-1)) < len(arr)。 //因为i会被j限度。 j越大。i能取的就越小。咱们只须要保障从i开始到完结的元素全笼罩就能够了。 //这里将范畴分成了两局部。 因为咱们基于2的幂。 其实就是参考二进制的性质。通过移位运算符能够进行二分。 dp[i][j] = rmq.withStrategy(i, j) } }}func (rmq *RMQ) withStrategy(i int, j int) int { return rmq.Dp[i][j-1] & rmq.Dp[i+(1<<(j-1))][j-1]}func (rmq *RMQ) withStrategyQuery(l int, r int, k int) int { return rmq.Dp[l][k] & rmq.Dp[r-(1<<k)+1][k]}func (rmq *RMQ) query(l int, r int) int { k := 0 for ; (1 << (k + 1)) <= r-l+1; k++ { } return rmq.withStrategyQuery(l, r, k)}算法逻辑（二分）
func closestToTarget(arr []int, target int) int { minVal := math.MaxInt32 rmq := RMQ{} tmp := make([]int, len(arr)+1) for k := 0; k < len(arr); k++ { tmp[k+1] = arr[k] } rmq.init(tmp) for r := 1; r < len(tmp); r++ { left := 1 right := r for left <= right { mid := left + (right-left)/2 res := rmq.query(mid, r) if res == target { return 0 } else if res > target { right = mid - 1 } else { left = mid + 1 } } if right == 0 { minVal = min(minVal, rmq.query(left, r)-target) } else if left == r+1 { minVal = min(minVal, target-rmq.query(right, r)) } else { minVal = min(min(rmq.query(left, r)-target, minVal), target-rmq.query(right, r)) } } return minVal}func min(x, y int) int { if x > y { return y } return x}