<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                企業??AI智能體構建引擎,智能編排和調試,一鍵部署,支持知識庫和私有化部署方案 廣告
                # 1131.絕對值表達式的最大值 ## 題目地址(1131. 絕對值表達式的最大值) <https://leetcode-cn.com/problems/maximum-of-absolute-value-expression/> ## 題目描述 ``` <pre class="calibre18">``` 給你兩個長度相等的整數數組,返回下面表達式的最大值: |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j| 其中下標 i,j 滿足 0 <= i, j < arr1.length。 示例 1: 輸入:arr1 = [1,2,3,4], arr2 = [-1,4,5,6] 輸出:13 示例 2: 輸入:arr1 = [1,-2,-5,0,10], arr2 = [0,-2,-1,-7,-4] 輸出:20 提示: 2 <= arr1.length == arr2.length <= 40000 -10^6 <= arr1[i], arr2[i] <= 10^6 ``` ``` ## 前置知識 - 數組 ## 解法一(數學分析) ## 公司 - 阿里 - 騰訊 - 字節 ### 思路 如圖我們要求的是這樣一個表達式的最大值。arr1 和 arr2 為兩個不同的數組,且二者長度相同。i 和 j 是兩個合法的索引。 > 紅色豎線表示的是絕對值的符號 ![](https://img.kancloud.cn/b6/ea/b6ea2bf03e5c749a654e761bfaaa2cba_936x142.jpg) 我們對其進行分類討論,有如下八種情況: > |arr1\[i\] -arr1\[j\]| 兩種情況 |arr2\[i\] -arr2\[j\]| 兩種情況 |i - j| 兩種情況 因此一共是 2 \* 2 \* 2 = 8 種 ![](https://img.kancloud.cn/5f/84/5f8490447c275a2e4fc63e20139f41ff_1060x1134.jpg) 由于 i 和 j 之前沒有大小關系,也就說二者可以相互替代。因此: - 1 等價于 8 - 2 等價于 7 - 3 等價于 6 - 4 等價于 5 也就是說我們只需要計算 1,2,3,4 的最大值就可以了。(當然你可以選擇其他組合,只要完備就行) 為了方便,我們將 i 和 j 都提取到一起: ![](https://img.kancloud.cn/b7/c7/b7c792ce47a56bde4ea4ea16f7abcd38_964x582.jpg) 容易看出等式的最大值就是前面的最大值,和后面最小值的差值。如圖: ![](https://img.kancloud.cn/a7/77/a7772b9252427ed8d7ef86549b142c17_974x732.jpg) 再仔細觀察,會發現前面部分和后面部分是一樣的,原因還是上面所說的 i 和 j 可以互換。因此我們要做的就是: - 遍歷一遍數組,然后計算四個表達式, arr1\[i\] + arr2\[i\] + i,arr1\[i\] - arr2\[i\] + i,arr2\[i\] - arr1\[i\] + i 和 -1 \* arr2\[i\] - arr1\[i\] + i 的 最大值和最小值。 - 然后分別取出四個表達式最大值和最小值的差值(就是這個表達式的最大值) - 四個表達式最大值再取出最大值 ### 關鍵點 - 數學分析 ### 代碼 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxAbsValExpr</span><span class="hljs-params">(self, arr1: List[int], arr2: List[int])</span> -> int:</span> A = [] B = [] C = [] D = [] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(len(arr1)): a, b, c, d = arr1[i] + arr2[i] + i, arr1[i] - arr2[i] + \ i, arr2[i] - arr1[i] + i, <span class="hljs-params">-1</span> * arr2[i] - arr1[i] + i A.append(a) B.append(b) C.append(c) D.append(d) <span class="hljs-keyword">return</span> max(max(A) - min(A), max(B) - min(B), max(C) - min(C), max(D) - min(D)) ``` ``` ## 解法二(曼哈頓距離) ### 思路 ![](https://img.kancloud.cn/79/b2/79b2b56d8f33a3420174034838b4ba28_309x368.jpg) (圖來自: [https://zh.wikipedia.org/wiki/%E6%9B%BC%E5%93%88%E9%A0%93%E8%B7%9D%E9%9B%A2)](https://zh.wikipedia.org/wiki/%E6%9B%BC%E5%93%88%E9%A0%93%E8%B7%9D%E9%9B%A2%EF%BC%89) 一維曼哈頓距離可以理解為一條線上兩點之間的距離: |x1 - x2|,其值為 max(x1 - x2, x2 - x1) ![](https://img.kancloud.cn/96/1a/961a24e8197fb17f27556e0f720e9479_756x166.jpg) 在平面上,坐標(x1, y1)的點 P1 與坐標(x2, y2)的點 P2 的曼哈頓距離為:|x1-x2| + |y1 - y2|,其值為 max(x1 - x2 + y1 - y2, x2 - x1 + y1 - y2, x1 - x2 + y2 - y1, x2 -x1 + y2 - y1) ![](https://img.kancloud.cn/6a/10/6a10a6d96941e954dc1e66f7e2a77509_998x778.jpg) 然后這道題目是更復雜的三維曼哈頓距離,其中(i, arr\[i\], arr\[j\])可以看作三位空間中的一個點,問題轉化為曼哈頓距離最遠的兩個點的距離。 延續上面的思路,|x1-x2| + |y1 - y2| + |z1 - z2|,其值為 : max( x1 - x2 + y1 - y2 + z1 - z2, x1 - x2 + y1 - y2 + z2 - z1, x2 - x1 + y1 - y2 + z1 - z2, x2 - x1 + y1 - y2 + z2 - z1, x1 - x2 + y2 - y1 + z1 - z2, x1 - x2 + y2 - y1 + z2- z1, x2 -x1 + y2 - y1 + z1 - z2, x2 -x1 + y2 - y1 + z2 - z1 ) 我們可以將 1 和 2 放在一起方便計算: max( x1 + y1 + z1 - (x2 + y2 + z2), x1 + y1 - z1 - (x2 + y2 - z2) ... ) 我們甚至可以擴展到 n 維,具體代碼見下方。 ### 關鍵點 - 曼哈頓距離 - 曼哈頓距離代碼模板 > 解題模板可以幫助你快速并且更少錯誤的解題,更多解題模板請期待我的[新書](https://lucifer.ren/blog/2019/12/11/draft/)(未完成) ### 代碼 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxAbsValExpr</span><span class="hljs-params">(self, arr1: List[int], arr2: List[int])</span> -> int:</span> <span class="hljs-title"># 曼哈頓距離模板代碼</span> sign = [<span class="hljs-params">1</span>, <span class="hljs-params">-1</span>] n = len(arr1) dists = [] <span class="hljs-title"># 三維模板</span> <span class="hljs-keyword">for</span> a <span class="hljs-keyword">in</span> sign: <span class="hljs-keyword">for</span> b <span class="hljs-keyword">in</span> sign: <span class="hljs-keyword">for</span> c <span class="hljs-keyword">in</span> sign: maxDist = float(<span class="hljs-string">'-inf'</span>) minDist = float(<span class="hljs-string">'inf'</span>) <span class="hljs-title"># 分別計算所有點的曼哈頓距離</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n): dist = arr1[i] * a + arr2[i] * b + i * c maxDist = max(maxDist, dist) minDist = min(minDist, dist) <span class="hljs-title"># 將所有的點的曼哈頓距離放到dists中</span> dists.append(maxDist - minDist) <span class="hljs-keyword">return</span> max(dists) ``` ``` **復雜度分析** - 時間復雜度:O(N3)O(N^3)O(N3) - 空間復雜度:O(N)O(N)O(N) ## 總結 可以看出其實兩種解法都是一樣的,只是思考角度不一樣。 ## 相關題目 - [1030. 距離順序排列矩陣單元格](https://leetcode-cn.com/problems/matrix-cells-in-distance-order/) ![](https://img.kancloud.cn/c9/34/c934fde4215a958b3078b40e7d269c8f_1201x719.jpg) - [1162. 地圖分析](https://leetcode-cn.com/problems/as-far-from-land-as-possible/) 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看