題目資訊

題目編號: 2873
題目連結: Maximum Value of an Ordered Triplet I
主題: Array

題目敘述

你有一個 0-索引 的整數陣列 nums。

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

索引三元組的值 $(i, j, k)$ 等於 $(\text{nums}[i] - \text{nums}[j]) \cdot \text{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 \leq \text{nums.length} \leq 100$
$1 \leq \text{nums}[i] \leq 10^6$

直覺

這個問題涉及在一個數組中找到三個索引 $(i, j, k)$ 之間通過特定運算獲得的最大值，且約束條件為 $i < j < k$。該運算的值定義為 $(\text{nums}[i] - \text{nums}[j]) \cdot \text{nums}[k]$。考慮到這些約束和定義，我們必須戰略性地探索這些三重組合的可能性，重點是最大化 $(i, j, k)$ 的結果。主要的挑戰在於高效地計算和更新潛在的最大三重組值，而不會過度重複迭代或重新計算。

解法

初始化變量：
- 開始時將 maxTripletValue 初始化為 0，用於保存任何有效三重組的最大值。
- 將 maxVal 設為 nums 的前兩個元素的最大值，以跟蹤迄今為止遇到的最大數。
- 計算 maxDifference，這是前兩個數字之間的差值 nums[0] - nums[1]，這對於評估潛在的三重組計算有所幫助。
遍歷數組：
- 從第三個元素（索引 2）開始遍歷至數組末尾，確保符合 $i < j < k$ 的條件。
評估當前三重組值：
- 對於每個索引 i 的元素，計算潛在的最大三重組值，通過評估 maxDifference * 當前元素（即 nums[i]），若新值更大則更新 maxTripletValue。
更新最大差值：
- 通過將當前值與 maxVal - 當前元素 進行比較來持續調整 maxDifference。這一步對於準備下一個潛在三重組的計算貢獻非常重要。
跟蹤最大元素：
- 更新 maxVal 為截至當前索引所見的最大值。這確保 maxVal 中總是包含我們計算中使用的索引的最大可能值。
返回結果：
- 當迴圈結束時，maxTripletValue 將包含從任何有效三重組中獲得的最大可能值。如果僅可能得到負值，它將保持 0，因為最初已初始化為 0。

此方法利用一次數組遍歷以計算所需結果，確保時間複雜度保持在 $O(n)$，其中 $n$ 是輸入數組 nums 的長度。

程式碼

C++

class Solution {
public:
    // 輔助函數，用於返回兩個值中的最大值
    long long max(long long a, long long b) {
        return a > b ? a : b;
    }

    // 函數用於查找任何(i, j, k)三元組的最大值，使得i < j < k
    long long maximumTripletValue(vector<int>& nums) {
        // 初始化三元組的最大值為0
        long long maxTripletValue = 0;

        // 初始化從前兩個元素找到的最大值
        long long maxVal = max(nums[0], nums[1]);

        // 初始化計算中遇到的最大差值
        long long maxDifference = nums[0] - nums[1];

        // 從第三個元素開始遍歷數組
        for (int i = 2; i < nums.size(); i++) {
            // 通過與(maxDifference * 當前元素)比較來更新最大三元組值
            maxTripletValue = max(maxTripletValue, maxDifference * nums[i]);

            // 更新maxDifference以保存其當前值與(maxVal - 當前元素)中的較大者
            maxDifference = max(maxDifference, maxVal - nums[i]);

            // 更新maxVal以保存迄今遇到的元素的最大值
            maxVal = max(maxVal, nums[i]);
        }

        // 返回找到的三元組的最大值
        return maxTripletValue;
    }
};

Python

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

    # 函數用於找出任何 (i, j, k) 組合的最大值，滿足 i < j < k
    def maximumTripletValue(self, nums: list[int]) -> int:
        # 初始化三元組的最大值為 0
        maxTripletValue = 0

        # 初始化目前為止從前兩個元素中找到的最大值
        maxVal = self.max(nums[0], nums[1])

        # 初始化為計算遇到的最大差異
        maxDifference = nums[0] - nums[1]

        # 從第三個元素開始遍歷數組
        for i in range(2, len(nums)):
            # 透過比較 (maxDifference * 當前元素) 更新最大三元組值
            maxTripletValue = self.max(maxTripletValue, maxDifference * nums[i])

            # 更新 maxDifference，以保存其當前值與 (maxVal - 當前元素) 中的最大值
            maxDifference = self.max(maxDifference, maxVal - nums[i])

            # 更新 maxVal，以保存截至目前所遇到元素的最大值
            maxVal = self.max(maxVal, nums[i])

        # 返回找到的三元組的最大值
        return maxTripletValue

複雜度分析

時間複雜度: 由於演算法對輸入數組 nums 進行一次迭代，且對每個元素進行恆定時間的操作，因此時間複雜度為 $O(n)$，其中 $n$ 是輸入數組的長度。
空間複雜度: 該演算法的空間複雜度為 $O(1)$，因為它僅使用固定數量的額外空間（即一些變數用於儲存中間結果），而與輸入大小無關。

CS Note
En

Leetcode 2873. Maximum Value of an Ordered Triplet I

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析