问题背景
给你一个下标从 0 0 0 开始的整数数组 n u m s nums nums。
请你从所有满足 i < j < k i \lt j \lt k i<j<k 的下标三元组 ( i , j , k ) (i, j, k) (i,j,k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 0 0。
下标三元组 ( i , j , k ) (i, j, k) (i,j,k) 的值等于 ( n u m s [ i ] − n u m s [ j ] ) × n u m s [ k ] (nums[i] - nums[j]) \times nums[k] (nums[i]−nums[j])×nums[k]。
数据约束
- 3 ≤ n u m s . l e n g t h ≤ 100 3 \le nums.length \le 100 3≤nums.length≤100
- 1 ≤ n u m s [ i ] ≤ 1 0 6 1 \le nums[i] \le 10 ^ 6 1≤nums[i]≤106
解题过程
这题可以枚举 j j j 也可以枚举 k k k，对于每一个 j j j 相应的位置而言，得出结果前需要知道前后缀最大值；枚举 k k k 时，则需要知道前缀的最大差值。
后缀最大值必须要通过预处理来计算，需要额外的空间，因此相对而言枚举 k k k 效率更高。
具体实现
枚举 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;}
}
