Leetcode 2673&2674 有序三元组中的最大值

本文最后更新于：2024年6月7日 中午

前言

这次的两道题目出leetcode周赛第 365 场周赛

由于t1和t2题目意思一样 这里就合并起来讲了

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

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

题目描述

给你一个下标从 0 开始的整数数组 nums 。

请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。

下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
示例 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 。

解题思路

暴力

初始化答案ans通过三层for枚举ijk并代入i<j<k和(nums[i] - nums[j]) * nums[k]

1
2
3
4
5
6
7
8
9
10
11
# 时间复杂度O(n的立方)
# 空间复杂度o(1)
class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        ans = 0
        for i in range(0,len(nums)):
            for j in range(0,len(nums)):
                for k in range(0,len(nums)):
                    if i < j < k:
                        ans = max(ans,(nums[i]-nums[j])*nums[k])
        return ans

由于t1的数据范围很小只有100 三层for循环遍历了100000次 是可以勉强通过的

但是到了t2的数据范围比较大 是100000我们再用t1的代码是无法通过的 因为遍历100000000次显然是不行的 因此我们需要空间换时间

前缀值

我们再把眼光看回这条公式

(nums[i] - nums[j]) * nums[k] i<j<k

对于这种情况 假设我们已知道了j 那问题是不是变成了找j-1中的最大i和j+1的最大k

变成两种条件

  • 找j-1 即j的左边的最大i
  • 找j+1 即j右边最大k

可以预处理这些信息

好 现在来看看代码怎么写

1
2
i_ = [0 for _ in range(0,len(nums))]
k_ = [0 for _ in range(0,len(nums))]

开两个数组 并全部初始化成0

分别从左到右更新i的最大值 从右到左更新k的最大值

1
2
3
4
5
6
7
8
9
10
i_ = [0 for _ in range(0,len(nums))]
k_ = [0 for _ in range(0,len(nums))]

i_[0] = nums[0]
for i in range(1,len(nums)):
    i_[i] = max(i_[i-1],nums[i])

k_[-1] = nums[-1]
for k in range(len(nums)-2,-1,-1):
    k_[k] = max(k_[k+1],nums[k])
  • i_ 代表j-1的最大i
  • k_代表j+1的最大k

开始枚举j 并初始化答案(ans) 代入公式不断更新最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 时间复杂度:O(n)
# 空间复杂度:O(n)
class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        i_ = [0 for _ in range(0,len(nums))]
        k_ = [0 for _ in range(0,len(nums))]

        i_[0] = nums[0]
        for i in range(1,len(nums)):
            i_[i] = max(i_[i-1],nums[i])

        k_[-1] = nums[-1]
        for k in range(len(nums)-2,-1,-1):
            k_[k] = max(k_[k+1],nums[k])
        
        ans = 0
        for j in range(1,len(nums)-1):
            ans = max(ans,(i_[j-1] - nums[j])* k_[j+1])
        return ans

t2就能过了

前缀值(优化)

我们注意到i_max是在前面获取的 也是从左到右遍历的 我们可以在更新ans的时候 把i_max也更新 这样开一个数组就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 时间复杂度:O(n)
# 空间复杂度:O(n)
class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        k_ = [0 for _ in range(0,len(nums))]

        k_[-1] = nums[-1]
        for k in range(len(nums)-2,-1,-1):
            k_[k] = max(k_[k+1],nums[k])
        
        ans = 0
        i_ = nums[0]
        for j in range(1,len(nums)-1):
            ans = max(ans,(i_ - nums[j])* k_[j+1])
            i_ = max(i_,nums[j])
        return ans

示例代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 时间复杂度:O(n)
# 空间复杂度:O(n)
class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        k_ = [0 for _ in range(0,len(nums))]

        k_[-1] = nums[-1]
        for k in range(len(nums)-2,-1,-1):
            k_[k] = max(k_[k+1],nums[k])
        
        ans = 0
        i_ = nums[0]
        for j in range(1,len(nums)-1):
            ans = max(ans,(i_ - nums[j])* k_[j+1])
            i_ = max(i_,nums[j])
        return ans

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 时间复杂度 O(n)
// 空间复杂度 O(n)
class Solution {
public:
    long long maximumTripletValue(vector<int>& nums) {
        int k[100001];
        long long ans = 0;
        long long i_ = nums[0];
        int n = nums.size();

        k[n-1] = nums[n-1];
        for(int i = n - 2; i >= 0; --i){
            k[i] = max(k[i+1],nums[i]);
        }

        for (int j = 1; j < n - 1; ++j){
            ans = max(ans,(i_ - nums[j]) * k[j+1]);
            i_ = max(i_,(long long)nums[j]);
        }
        return ans;
    }
};

后记

多动手，多思考

leetcode
#leetcode #code #动态规划
Leetcode 2673&2674 有序三元组中的最大值
http://blog.bingyue.top/2023/10/21/leetcode2873&2874/
作者
bingyue
发布于
2023年10月21日
许可协议