2874 有序三元组中的最大值

· 2025-4-2   · 次阅读   · 字数统计: 188字   · 阅读时长≈ 1分钟

  · 算法题解   · LeetCode

题目链接

2873. 有序三元组中的最大值 I

2874. 有序三元组中的最大值 II

分析

要想使得三元组的计算值最大，那么就要使 $nums[i]$ 和 $nums[k]$ 的值最大

维护前缀最大值和后缀最大值，枚举 $j$ 即可算出最大值

代码实现

class Solution {
public:
    long long maximumTripletValue(vector<int>& nums) {
        int n = nums.size(), pre = 0;
        long long ans = 0;
        vector<int> suf(n, 0);
        suf[n - 1] = nums[n - 1];

        for(int i = n - 2; ~i; --i) {
            suf[i] = max(suf[i + 1], nums[i]);
        }

        for(int i = 1; i < n - 1; ++i) {
            pre = max(pre, nums[i - 1]);
            ans = max(ans, 1ll * (pre - nums[i]) * suf[i + 1]);
        }

        return ans;
    }
};

复杂度分析

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$