主題
題目連結(jié)：
題目意譯：
你被給定一個(gè)索引值從 0 開始且長度為 n 的整數(shù)陣列 nums、一個(gè)整數(shù) indexDifference 以及另一個(gè)整數(shù) valueDifference。
你的任務(wù)是找到兩個(gè)索引值 i 和 j，兩者都位於範(fàn)圍 [0, n - 1] 中，並滿足以下條件：
abs(i - j) ≧ indexDifference，且
abs(nums[i] - nums[j]) ≧ valueDifference
回傳一個(gè)整數(shù)陣列 answer，其中如果存在上述的兩個(gè)索引值，則 answer = [i, j]；反之，則 answer = [-1, -1]。如果所有兩個(gè)索引值有多種可能的選擇，則回傳任意一個(gè)。
注： i 和 j 可能相等。
限制：
1 ≦ n == nums.length ≦ 10 ^ 5
0 ≦ nums[i] ≦ 10 ^ 9
0 ≦ indexDifference ≦ 10 ^ 5
0 ≦ valueDifference ≦ 10 ^ 9
範(fàn)例測資：
範(fàn)例 1：
輸入： nums = [5,1,4,1], indexDifference = 2, valueDifference = 4
輸出： [0,3]
解釋： 在此例中，可以選擇 i = 0 且 j = 3。
abs(0 - 3) ≧ 2 and abs(nums[0] - nums[3]) ≧ 4。
因此一個(gè)合法的答案為 [0,3]。
[3,0] 也是一個(gè)合法的答案。
範(fàn)例 2：
輸入： nums = [2,1], indexDifference = 0, valueDifference = 0
輸出： [0,0]
解釋： 在此例中，可以選擇 i = 0 且 j = 0。
abs(0 - 0) ≧ 0 and abs(nums[0] - nums[0]) ≧ 0。
因此一個(gè)合法的答案為 is [0,0]。
其他合法的答案為 [0,1] 、 [1,0] 和 [1,1]。
範(fàn)例 3：
輸入： nums = [1,2,3], indexDifference = 2, valueDifference = 4
輸出： [-1,-1]
解釋： 在此例中，可以證明不可能找到同時(shí)滿足兩個(gè)條件的索引值。
因此回傳 [-1,-1]。
解題思維：
首先觀察 abs(i - j) ≧ indexDifference 代表的意義。如果我們固定 i 值，則 j 會(huì)滿足「j ≦ i - indexDifference」或是「i + indexDifference ≦ j」。
如果對於單一一個(gè)元素 nums[i] 我們知道 nums[0] ~ nums[i - indexDifference] 的最小值和最大值（依序稱為 mL 和 ML）以及 nums[i + indexDifference] ~ nums[n - 1] 的最小值和最大值（依序稱為 mR 和 MR）。則對於 nums[i] 來說，最有可能符合條件的 abs(nums[i] - mL) 、 abs(nums[i] - ML) 、 abs(nums[i] - mR) 和 abs(nums[i] - MR)。
而如果我們對每一個(gè)元素都知道以上的資訊，則必定可以找到所求。如果找不到就代表 nums 中真的不存在任何符合條件的索引值。
而可以看到 nums[0] ~ nums[i - indexDifference] 和 nums[i + indexDifference] ~ nums[n - 1] 對於 nums[i] 來說，一個(gè)在「左邊」、一個(gè)在「右邊」。因此我們可以先把左右分開判斷，如這題也有做類似的事情。
假設(shè)現(xiàn)在看的是「左邊」，則觀察 nums[i] 與 nums[i + 1] 會(huì)需要考慮到的元素差別。可以看到後者只會(huì)比前者多 nums[i - indexDifference + 1] 要考慮而已。因此實(shí)際上 nums[i + 1] 可以直接繼承 nums[i] 看到的最小值、最大值，然後再跟 nums[i - indexDifference + 1] 比大小並更新最小值最大值即可得知 nums[i + 1] 所需的資訊。
所以從 nums[indexDifference] 開始掃到 nums[n - 1] 並按照上面的最小值最大值更新方式即可知道每一個(gè)元素「左邊」的最小值最大值。
而「右邊」也是同理。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
