class Solution {
public:
long long maximumTripletValue(vector<int>& nums) {
}
};
100086. 有序三元组中的最大值 II
给你一个下标从 0 开始的整数数组 nums 。
请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。
下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * 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 <= nums.length <= 1051 <= nums[i] <= 106原站题解
golang 解法, 执行用时: 112 ms, 内存消耗: 8.4 MB, 提交时间: 2023-10-02 00:21:40
// 枚举j
func maximumTripletValue1(nums []int) int64 {
ans := 0
n := len(nums)
sufMax := make([]int, n+1)
for i := n - 1; i > 1; i-- {
sufMax[i] = max(sufMax[i+1], nums[i])
}
preMax := 0
for j, x := range nums {
ans = max(ans, (preMax-x)*sufMax[j+1])
preMax = max(preMax, x)
}
return int64(ans)
}
// 枚举k
func maximumTripletValue(nums []int) int64 {
ans, maxDiff, preMax := 0, 0, 0
for _, x := range nums {
ans = max(ans, maxDiff*x)
maxDiff = max(maxDiff, preMax-x)
preMax = max(preMax, x)
}
return int64(ans)
}
func max(a, b int) int { if b > a { return b }; return a }
java 解法, 执行用时: 1 ms, 内存消耗: 56.8 MB, 提交时间: 2023-10-02 00:18:38
class Solution {
// 枚举j
public long maximumTripletValue1(int[] nums) {
int n = nums.length;
int[] sufMax = new int[n + 1];
for (int i = n - 1; i > 1; i--) {
sufMax[i] = Math.max(sufMax[i + 1], nums[i]);
}
long ans = 0;
int preMax = nums[0];
for (int j = 1; j < n - 1; j++) {
ans = Math.max(ans, (long) (preMax - nums[j]) * sufMax[j + 1]);
preMax = Math.max(preMax, nums[j]);
}
return ans;
}
// 枚举k
public long maximumTripletValue(int[] nums) {
long ans = 0;
int maxDiff = 0, preMax = 0;
for (int x : nums) {
ans = Math.max(ans, (long) maxDiff * x);
maxDiff = Math.max(maxDiff, preMax - x);
preMax = Math.max(preMax, x);
}
return ans;
}
}
cpp 解法, 执行用时: 132 ms, 内存消耗: 88.1 MB, 提交时间: 2023-10-02 00:18:01
class Solution {
public:
// 枚举j
long long maximumTripletValue(vector<int> &nums) {
int n = nums.size();
vector<int> suf_max(n + 1, 0);
for (int i = n - 1; i > 1; i--) {
suf_max[i] = max(suf_max[i + 1], nums[i]);
}
long long ans = 0;
int pre_max = nums[0];
for (int j = 1; j < n - 1; j++) {
ans = max(ans, (long long) (pre_max - nums[j]) * suf_max[j + 1]);
pre_max = max(pre_max, nums[j]);
}
return ans;
}
// 枚举k
long long maximumTripletValue2(vector<int> &nums) {
long long ans = 0;
int max_diff = 0, pre_max = 0;
for (int x : nums) {
ans = max(ans, (long long) max_diff * x);
max_diff = max(max_diff, pre_max - x);
pre_max = max(pre_max, x);
}
return ans;
}
};
python3 解法, 执行用时: 232 ms, 内存消耗: 28.4 MB, 提交时间: 2023-10-02 00:17:20
class Solution:
# 枚举j
def maximumTripletValue1(self, nums: List[int]) -> int:
n = len(nums)
suf_max = [0] * (n + 1)
for i in range(n - 1, 1, -1):
suf_max[i] = max(suf_max[i + 1], nums[i])
ans = pre_max = 0
for j, x in enumerate(nums):
ans = max(ans, (pre_max - x) * suf_max[j + 1])
pre_max = max(pre_max, x)
return ans
# 枚举k
def maximumTripletValue(self, nums: List[int]) -> int:
ans = max_diff = pre_max = 0
for x in nums:
ans = max(ans, max_diff * x)
max_diff = max(max_diff, pre_max - x)
pre_max = max(pre_max, x)
return ans