題目資訊

• 題目編號: 2874
• 題目連結: Maximum Value of an Ordered Triplet II
• 主題: Array

題目敘述

你有一個0索引的整數數組 nums。

返回所有索引三元組 (i, j, k) 的最大值，使得 $i < j < k$。如果所有這樣的三元組值為負數，則返回 0。

索引三元組的值 (i, j, k) 等於 $(\text{nums}[i] - \text{nums}[j]) \times \text{nums}[k]$。

範例 1:

輸入: nums = [12,6,1,2,7]
輸出: 77
解釋: 三元組 (0, 2, 4) 的值為 $(\text{nums}[0] - \text{nums}[2]) \times \text{nums}[4] = 77$。
可以證明，沒有順序索引三元組的值大於 77。

範例 2:

輸入: nums = [1,10,3,4,19]
輸出: 133
解釋: 三元組 (1, 2, 4) 的值為 $(\text{nums}[1] - \text{nums}[2]) \times \text{nums}[4] = 133$。
可以證明，沒有順序索引三元組的值大於 133。

範例 3:

輸入: nums = [1,2,3]
輸出: 0
解釋: 唯一的順序索引三元組 (0, 1, 2) 的值為負數 $(\text{nums}[0] - \text{nums}[1]) \times \text{nums}[2] = -3$。因此，答案為 0。

約束條件:

• $3 \leq \text{nums.length} \leq 10^5$
• $1 \leq \text{nums}[i] \leq 10^6$

直覺

此問題要求我們在陣列 nums 中找到所有索引三元組 $(i, j, k)$ 所能夠達到的最大值，其中 $i < j < k$。關鍵在於理解三元組的數值本質，其定義為 $(\text{nums}[i] - \text{nums}[j]) \times \text{nums}[k]$。這個方程式包含兩個部分：一個差 $(\text{nums}[i] - \text{nums}[j])$，當第一個數字遠大於第二個時其值被最大化，以及一個乘數 $\text{nums}[k]$，其應該要盡可能地大。我們的策略包括在遍歷陣列的過程中預處理潛在的最大值和差異，以便高效地計算此三元組的數值。

解法

解決此問題的方法是使用一次遍歷（$O(n)$時間複雜度）來動態計算最大三元組的數值：

1. 初始化：首先將變數 answer 初始化為零，這將用來儲存目前為止找到的最大三元組值。同時設定兩個其他的關鍵變數：max_val，其儲存了前兩個元素中的最大值，以及 diff，其初始化為前兩個元素的差值 ($\text{nums}[0] - \text{nums}[1]$)。

2. 迭代計算：從陣列的第三個元素（索引 2）開始迭代。

   • 三元組值計算：對於每個新的元素（作為 $\text{nums}[k]$），利用預先計算的 diff 來計算三元組的數值，即 $(\text{nums}[i] - \text{nums}[j]) \times \text{nums}[k]$。用其與當前的 answer 的最大值來更新 answer。
   • 更新差值：同時維護未來迭代的最佳 diff，這涉及到將 diff 更新為其本身與當前元素的 max_val - \text{nums}[i] 之較大者。
   • 更新最大值：將 max_val 更新為其本身與目前元素 \text{nums}[i] 中的較大者，確保其代表至目前為止遇到的最大值，以用於未來可能的 i 索引。

3. 結果：到迭代結束時，answer 中包含了最大三元組的數值；返回此值作為最終輸出。

此方法有效地利用了先前計算的最佳可能差值，以及在遍歷中保持跟蹤的最大值，讓我們能夠智能且高效地評估潛在的三元組組合。如果所有此類評估得出的三元組值均為負值，那麼初始化為零的 answer 值將保持不變，從而符合問題的要求。

程式碼

C++

class Solution {
public:
    // 函數返回兩個 long long 整數中的最大值
    long long max(long long a, long long b) { 
        return a > b ? a : b; 
    }
    
    // 根據給定條件找到最大三元組值的函數
    long long maximumTripletValue(vector<int>& nums) {
        // 初始化答案並計算 max_val 和 diff 的初始值
        long long answer = 0;
        long long max_val = max(nums[0], nums[1]);
        long long diff = nums[0] - nums[1];

        // 從第三個元素開始遍歷 nums 陣列
        for (int i = 2; i < nums.size(); i++) {
            // 通過檢查當前的三元組值來更新答案
            answer = max(answer, diff * nums[i]);
            // 更新下個潛在三元組的 diff
            diff = max(diff, max_val - nums[i]);
            // 更新 max_val 以供未來計算使用
            max_val = max(max_val, nums[i]);
        }

        // 返回計算出的最大三元組值
        return answer;
    }
};

Python

class Solution:
    # 函數用於返回兩個整數中的最大值
    def max(self, a, b):
        return a if a > b else b

    # 函數用於根據給定條件找到最大三元組值
    def maximumTripletValue(self, nums):
        # 初始化答案並計算 max_val 和 diff 的初始值
        answer = 0
        max_val = self.max(nums[0], nums[1])
        diff = nums[0] - nums[1]

        # 從第三個元素開始遍歷 nums 陣列
        for i in range(2, len(nums)):
            # 通過檢查當前三元組的值來更新答案
            answer = self.max(answer, diff * nums[i])
            # 更新 diff 以用於下一個可能的三元組
            diff = self.max(diff, max_val - nums[i])
            # 更新 max_val 以便未來使用
            max_val = self.max(max_val, nums[i])

        # 返回計算出的最大三元組值
        return answer

複雜度分析

• 時間複雜度: $O(n)$

  演算法的時間複雜度為 $O(n)$，其中 $n$ 是 nums 陣列的長度。這是因為該函數僅遍歷 nums 陣列一次，從第三個元素（索引為 2）開始直到結束。每次迭代涉及常數時間操作，例如更新變數和調用 max 函數（該函數只涉及比較操作，因此是在常數時間內完成）。

• 空間複雜度: $O(1)$

  演算法的空間複雜度為 $O(1)$，因為它使用的額外空間量是固定的，與輸入大小無關。演算法僅需為一些變數分配空間，具體包括 answer、max_val 和 diff，這些變數儲存的是整數或計算出的值。未使用任何隨著輸入大小增長的額外資料結構。