LeetCode 🟡 2874. Maximum Value of an Ordered Triplet II

🔗 🟡 2874. Maximum Value of an Ordered Triplet II 1583

tags: Weekly Contest 365 陣列(Array) 貪心(Greedy) 前後綴分解

題意

給定一個下標從 $0$ 開始的整數陣列 $nums$ 。

返回 $\max(0, \displaystyle\max_{0 \leq i < j < k < n} (nums[i] - nums[j]) \times nums[k])$

思路：貪心(Greedy)

為了使 $(nums[i] - nums[j]) \times nums[k]$ 盡可能大，直覺上我們希望：

1. $nums[i] - nums[j]$ 越大越好：也就是 $nums[i]$ 盡可能大，而 $nums[j]$ 盡可能小
2. $nums[k]$ 越大越好

由於索引的限制條件 $i < j < k$，我們需要依序考慮如何選擇 $i$、$j$ 和 $k$。

由於需要滿足 $i < j < k$，所以又有兩種思路

1. 枚舉 $nums[j]$，然後找最大的 $nums[i]$ 和 $nums[k]$，可以透過前後綴分解實現
2. 枚舉 $nums[k]$，維護前綴中的最大差值 $(nums[i] - nums[j])$，並維護前綴中最大的 $nums[i]$ 以更新最大差值

方法一：枚舉 $nums[j]$ - 前後綴分解

注意到我們希望位於兩側的 $nums[i]$ 和 $nums[k]$ 盡可能的大，因此可以從 $nums[j]$ 的角度思考。

對於每個 $nums[j]$，我們希望找到前面最大的 $nums[i]$ 和後面最大的 $nums[k]$，這樣就可以得到最大的 $(nums[i] - nums[j]) \times nums[k]$。

為了維護這些元素，我們可以維護前綴最大值和後綴最大值。此外，前綴最大值可以在遍歷 $j$ 的過程中順便維護。

複雜度分析

• 時間複雜度：$\mathcal{O}(n)$
• 空間複雜度：$\mathcal{O}(n)$

PythonC++

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums)
        suf = [0] * n
        suf[-1] = nums[-1]  # 後綴最大值
        for i in range(n - 2, -1, -1):
            suf[i] = max(suf[i + 1], nums[i])
        ans = 0
        pre_mx = nums[0]  # 前綴最大值
        for i in range(1, n - 1):
            ans = max(ans, (pre_mx - nums[i]) * suf[i + 1])
            pre_mx = max(pre_mx, nums[i])
        return ans

class Solution {
public:
    long long maximumTripletValue(vector<int>& nums) {
        int n = nums.size();
        vector<int> suf(n);
        suf[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) suf[i] = max(suf[i + 1], nums[i]);
        long long ans = 0;
        int pre_mx = nums[0];
        for (int i = 1; i < n - 1; i++) {
            ans = max(ans, (long long)(pre_mx - nums[i]) * suf[i + 1]);
            pre_mx = max(pre_mx, nums[i]);
        }
        return ans;
    }
};

方法二：枚舉 $nums[k]$ - 一次遍歷

類似地，我們也可以從 $nums[k]$ 的角度思考。

• 對於每個 $nums[k]$，我們希望找到前面最大的 $nums[i] - nums[j]$。
• 為此，我們可以使用一個變數 $mx\_diff$ 來維護前綴最大差值。

接著我們考慮 $mx\_diff = nums[i] - nums[j]$ 的更新：

• 此時我們又可以從 $nums[j]$ 的角度思考，我們希望可以找到最大的 $nums[i]$，這樣就可以得到最大的 $mx\_diff$。
• 為此，我們可以使用一個變數 $mx$ 來維護前綴最大值。

最後，我們只需要在遍歷的過程中不斷更新答案即可，當我們遍歷到新元素 $x$ 時：

1. 將 $x$ 視為 $nums[k]$，則可以計算可能的最大結果 $(mx\_diff) \times x$
2. 將 $x$ 視為 $nums[j]$，則可以更新前綴最大差值 $mx\_diff = mx - x$
3. 將 $x$ 視為 $nums[i]$，則可以更新前綴最大值 $mx$

複雜度分析

• 時間複雜度：$\mathcal{O}(n)$
• 空間複雜度：$\mathcal{O}(1)$

PythonC++

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        ans = 0
        mx = mx_diff = float('-inf')
        for x in nums:
            ans = max(ans, mx_diff * x)
            mx_diff = max(mx_diff, mx - x)  # (nums[i] - nums[j])
            mx = max(mx, x)  # nums[i]
        return ans

class Solution {
public:
    long long maximumTripletValue(vector<int>& nums) {
        int mx = LLONG_MIN / 2, mx_diff = LLONG_MIN / 2;
        long long ans = 0;
        for (int x : nums) {
            ans = max(ans, (long long)mx_diff * x);
            mx_diff = max(mx_diff, mx - x);  // (nums[i] - nums[j])
            mx = max(mx, x);  // nums[i]
        }
        return ans;
    }
};

---

寫在最後

PROMPT

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant colors, anime style,

1girl, solo, Ganyu, Ganyu (Genshin Impact), long hair, light blue hair, purple eyes, black-red horns, yellow jacket, white shirt, black skirt, looking at viewer, smile, outdoors, yellow tulips, flower field, sunlight,

The image depicts an anime-style Ganyu from Genshin Impact, but with a different outfit and setting. She is wearing a yellow jacket over a white shirt, black skirt, and is standing in a field of yellow tulips. The sun is shining, creating a warm and inviting atmosphere, and she’s smiling at the viewer.