共计 3040 个字符，预计需要花费 8 分钟才能阅读完成。
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
}
