前言

僅做學習使用，侵刪

什么是ARTS？

算法(Algorithm): 每周至少一道LeetCode算法題，加強編程訓練和算法學習

閱讀(Review)： 閱讀并點評至少一篇英文技術文章，提高英文水平

技巧 (Tip)：學習至少一個技術技巧，總結、歸納日常工作中遇到的知識點

分享(Share)：分析一篇有關點和思考的技術文章，建立影響力，輸出價值觀

算法(Algorithm)

2873.有序三元組中的最大值!

題目描述

給你一個下標從 0 開始的整數數組 nums 。
請你從所有滿足 i < j < k 的下標三元組 (i, j, k) 中，找出并返回下標三元組的最大值。如果所有滿足條件的三元組的值都是負數，則返回 0 。
下標三元組 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。示例 1：
輸入：nums = [12,6,1,2,7]
輸出：77
解釋：下標三元組 (0, 2, 4) 的值是 (nums[0] - nums[2]) * nums[4] = 77 。
可以證明不存在值大于 77 的有序下標三元組。
示例 2：
輸入：nums = [1,10,3,4,19]
輸出：133
解釋：下標三元組 (1, 2, 4) 的值是 (nums[1] - nums[2]) * nums[4] = 133 。
可以證明不存在值大于 133 的有序下標三元組。 
示例 3：
輸入：nums = [1,2,3]
輸出：0
解釋：唯一的下標三元組 (0, 1, 2) 的值是一個負數，(nums[0] - nums[1]) * nums[2] = -3 。因此，答案是 0 。提示：
? 3 <= nums.length <= 100
? 1 <= nums[i] <= 106

解題方法

方法一:暴力求解

思路

枚舉所有滿足 i<j<k 的三元組 (i,j,k)，返回所有值大于等于 0 的三元組的最大值。

class Solution {public long maximumTripletValue(int[] nums) {int n = nums.length;long res = 0;for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {for (int k = j + 1; k < n; k++) {res = Math.max(res, (long) (nums[i] - nums[j]) * nums[k]);}}}return res;}
}

復雜度分析

• 時間復雜度：O(n3)，其中 n 是數組 nums 的長度。
• 空間復雜度：O(1)。

方法二：貪心

思路

固定三元組 (i,j,k) 的 j 和 k 時，由值公式 (nums[i]?nums[j])×nums[k] 可知，nums[i] 取區間 [0,j) 內的最大值時，(nums[i]?nums[j])×nums[k] 最大。使用兩層循環分別枚舉 k 和 j，同時使用 m 維護 [0,j) 的最大值，返回所有 (m?nums[j])×nums[k] 的最大值（若所有值都為負數，則返回 0）。

class Solution {public long maximumTripletValue(int[] nums) {int n = nums.length;long res = 0;for (int k = 2; k < n; k++) {int m = nums[0];for (int j = 1; j < k; j++) {res = Math.max(res, (long)(m - nums[j]) * nums[k]);m = Math.max(m, nums[j]);}}return res;}
}

復雜度分析

• 時間復雜度：O(n2)，其中 n 是數組 nums 的長度。
• 空間復雜度：O(1)。

方法三：貪心 + 前后綴數組

思路

令數組 nums 的長度為 n。根據值公式 (nums[i]?nums[j])×nums[k] 可知，當固定 j 時，nums[i] 和 nums[k] 分別取 [0,j) 和 [j+1,n) 的最大值時，三元組的值最大。我們使用 leftMax[j] 和 rightMax[j] 維護前綴 [0,j) 最大值和后綴 [j+1,n) 最大值，依次枚舉 j，計算值 (leftMax[j]?nums[j])×rightMax[j]，返回最大值（若所有值都為負數，則返回 0）。

public class Solution {public long maximumTripletValue(int[] nums) {int n = nums.length;int[] leftMax = new int[n];int[] rightMax = new int[n];for (int i = 1; i < n; i++) {leftMax[i] = Math.max(leftMax[i - 1], nums[i - 1]);rightMax[n - 1 - i] = Math.max(rightMax[n - i], nums[n - i]);}long res = 0;for (int j = 1; j < n - 1; j++) {res = Math.max(res, (long)(leftMax[j] - nums[j]) * rightMax[j]);}return res;}
}

復雜度分析

• 時間復雜度：O(n)，其中 n 是數組 nums 的長度。
• 空間復雜度：O(n)。

方法四：貪心

思路

類似于方法三，我們固定 k，那么當 nums[i]?nums[j] 取最大值時，三元組的值最大。我們可以用 imax 維護 nums[i] 的最大值，dmax 維護 nums[i]?nums[j] 的最大值，在枚舉 k 的過程中，更新 dmax 和 imax。

class Solution {public long maximumTripletValue(int[] nums) {int n = nums.length;long res = 0, imax = 0, dmax = 0;for (int k = 0; k < n; k++) {res = Math.max(res, dmax * nums[k]);dmax = Math.max(dmax, imax - nums[k]);imax = Math.max(imax, nums[k]);}return res;}
}

復雜度分析

• 時間復雜度：O(n)，其中 n 是數組 nums 的長度。
• 空間復雜度：O(1)。

分享(Share)

文章閱讀

BeanUtils對比 12 種 Bean 自動映射工具，就它性能最拉跨_java beanutils modelmapper-CSDN博客

危險！請馬上替換代碼中的BeanUtils！！！

因為現在系統中正在使用BeanUtils 看到文章，但是經過詢問基本不會出現這種問題

接口 TPS是什么

接口 TPS（Transactions Per Second）是指每秒鐘系統能夠處理的接口事務數量，它是衡量系統性能的重要指標之一。一個事務是指一個客戶端向服務器發送請求，服務器進行處理并返回響應的完整過程。在接口性能測試中，TPS 常被用來評估接口的處理能力。TPS 值越高，說明系統在單位時間內能夠處理更多的事務，性能越好

參考資料

作者：力扣官方題解

鏈接：2873. 有序三元組中的最大值 I - 力扣（LeetCode）

來源：力扣（LeetCode）

著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。