題目連結:
題目意譯:
兩個數對 (a, b) 和 (c, d) 的乘積差定義為 (a × b) - (c × d)。
例如,(5, 6) 和 (2, 7) 的乘積差為 (5 × 6) - (2 × 7) = 16。
給定一整數陣列 nums,選擇四個相異索引值 w 、 x 、 y 和 z 使得數對 (nums[w], nums[x]) 和 (nums[y], nums[z]) 的乘積差最大化。
回傳乘積差之最大值。
限制:
4 ≦ nums.length ≦ 10 ^ 4
1 ≦ nums[i] ≦ 10 ^ 4
範例測資:
範例 1:
輸入: nums = [5,6,2,7,4]
輸出: 34
解釋: 我們可以選擇索引值 1 和 3 為第一個數對 (6, 7) 以及索引值 2 和 4 為第二個數對 (2, 4)。
乘積差為 (6 × 7) - (2 × 4) = 34。
範例 2:
輸入: nums = [4,2,5,9,7,4,8]
輸出: 64
解我們可以選擇索引值 3 和 6 為第一個數對 (9, 8) 以及索引值 1 和 5 為第二個數對 (2, 4)。
乘積差為 (9 × 8) - (2 × 4) = 64。
解題思維:
可以看到數對中的數字順序並不重要,例如 (8, 9) 跟 (9, 8) 的乘積值是相同的(整數乘法之可交換性)。
而要使一個式子 a - b 最大化的話就是讓 a 盡量大、 b 盡量小。也就是 nums[w] × nums[x] 盡量大、 nums[y] × nums[z] 盡量小。
再加上本題給定的數字都是正整數,因此我們可以從 nums 中取兩個最大的數字作為 nums[w] × nums[x] 、兩個最小的數字為 nums[y] × nums[z]。兩者相減即是所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。