1.概述
這篇blog來源于leetcode。參加了第198場周賽，結果比前幾次周賽慘很多。不過沒關系，及時發現了自己很菜，路漫漫其修遠兮！這邊blog主要是針對周賽第四題衍發出來的思考。主要包括RMQ問題以及自己思考題目的過程。價值不是很大，随便寫寫。
2.RMQ問題
RMQ（Range Minimum / Maximum Query ）主要是用來求區間最值問題研究出來的算法。
對于RMQ問題有很多方法可以求解，比如線段樹，或者使用動态規劃。對于靜态區間的RMQ問題，使用DP是非常好了解的。下面我們就來聊聊。
舉個簡單的例子
比如給定一個無序數組arr。求數組所有區間的最值。如果通過暴力枚舉，肯定會TLE。但是我們很容易想到。對于一個大的區間[0,1]，我們可以将其分為兩個子區間:[0,1]和[2,3]。那麼大區間的最值，其實可以通過兩個子區間得到。
使用動态規劃的思想
大問題的結果依賴若幹個子問題。
既然使用動态規劃，我們就需要列出狀态轉移方程。
我們令dp[i][j]表示：以第i個數為起點，連續2^j個數 的區間最值。比如dp[2][1]就是區間[2,3]的最值。3怎麼來。其實就是2+2^1-1 ，減1時減掉第一個數。
接下來我們考慮一下邊界條件（對于動态規劃，邊界條件是解決問題的突破口）
依據上面定義：dp[i][0]代表數組第i個數開始，連續一個數的區間的最值。連續一個數，其實就隻有一個，就是他本身。
是以我們得到,這裡我們假設數組arr 是從1開始。
推導轉移方程
對于dp[i][j]，我們如何做求值？
其實可以将這個區間分為2部分。第一部分為dp[i][j-1]，第二部分為dp[i+(1<<(j-1))][j-1]。然後依賴兩個區間的結果再求大區間的最值。
大家看到這兩個區間可能很懵逼。不着急看，我們一個一個來分析。
- 首先是dp[i][j-1]，這個區間我們應該很容易了解。就是以i開始，共2(j-1)個數。其實就是以i開始，2j的前半部分。因為2(j-1)是2j的一半。
- 其次是dp[i+(1<<(j-1))][j-1]。這個看起來複雜。但從上可知，這個表示的就是剩餘半個區間的最值。我們根據dp的定義來推到一下。後半部分區間就是從前半個區間最後一個元素的後一個元素到區間末尾。那麼我們就需要計算一下後半個區間的開始位置。其實就是大區間初始位置i+區間長度的一半。長度計算依賴j。是以就可以得到是i+(1<<(j-1))。
這裡的思想就是一分為2。前提是分出來的區間的結果是提前知道的。
是以我們可以得到狀态轉移方程(以區間最大值舉例)：
查詢最值
通過上面過程，我們将最值計算出來，但是我們如何擷取結果呢？
我們假設len為要查詢區間的長度。我們log(len)也就是我們dp[i][j]中j的長度。但是我們并不能保證2^log(len)==len。因為len不一定是2的整數幂。是以我們并不能保證區間的完整性。
如果該長度正好是2的幂。那麼沒毛病，結果為dp[i][log(len)]，否則我們會遺漏一些區間，如下圖。那麼如何解決問題呢？
大家可以看到我們可以使用dp[i][log(len)]和dp[r-(1<<k)+1][k]。使用後者是為了補充我們的遺漏。但是大家可能會擔心有重複。但是如果是求最值問題，重複是不會影響結果的。是以，很ok。
3.比賽題目分析
題目連結：
https://leetcode-cn.com/problems/find-a-value-of-a-mysterious-function-closest-to-target/
題目分析：
我們對函數分析後，發現對于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
}