安远网络推广公司_哈尔滨互联网公司_谷歌官方网站首页_百度可以发布广告吗

问题背景

给你一个下标从 $0$ 开始的整数数组 $nums$。
请你从所有满足 $i<j<k$ 的下标三元组 $(i,j,k)$ 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 $0$。
下标三元组 $(i,j,k)$ 的值等于 $(nums[i]-nums[j])\times nums[k]$。

数据约束

• $3\le nums.length\le 10^5$
• $1\le nums[i]\le 10^6$

解题过程

和 昨天的题 一样，只有数据范围不同。由于使用的方法已经达到了 $O(N)$ 这个量级，可以用完全一样的方法来解决。

具体实现

枚举 j

class Solution {public long maximumTripletValue(int[] nums) {int n = nums.length;long res = 0;int[] sufMax = new int[n];sufMax[n - 1] = nums[n - 1];for (int i = n - 2; i >= 0; i--) {sufMax[i] = Math.max(sufMax[i + 1], nums[i]);}int preMax = nums[0];for (int j = 1; j < n - 1; j++) {res = Math.max(res, (long) (preMax - nums[j]) * sufMax[j + 1]);preMax = Math.max(preMax, nums[j]);}return res;}
}

枚举 k

class Solution {public long maximumTripletValue(int[] nums) {long res = 0;int maxDiff = 0;int preMax = 0;for (int num : nums) {res = Math.max(res, (long) maxDiff * num);maxDiff = Math.max(maxDiff, preMax - num);preMax = Math.max(preMax, num);}return res;}
}