LC.P2874[有序三元组中的最大值II]

方法一：贪心+前后缀数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public long maximumTripletValue(int[] nums) {
        int n = nums.length;
        int[] leftMax = new int[n]; // [0, i)的最大值
        int[] rightMax = new int[n]; // (i, n)的最大值

        for (int i = 1; i < n; ++i) {
            leftMax[i] = Math.max(leftMax[i - 1], nums[i - 1]);
            rightMax[n - i - 1] = Math.max(rightMax[n - i], nums[n - i]);
        }
        long ans = 0;
        for (int j = 1; j < n - 1; ++j) {
            ans = Math.max(ans, (long) (leftMax[j] - nums[j]) * rightMax[j]);
        }
        return ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

方法二：贪心+后缀数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public long maximumTripletValue(int[] nums) {
        int n = nums.length;
        int[] rightMax = new int[n]; // (i, n)的最大值

        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = Math.max(rightMax[i + 1], nums[i + 1]);
        }
        long ans = 0;
        int leftMax = nums[0];
        for (int j = 1; j < n - 1; ++j) {
            ans = Math.max(ans, (long) (leftMax - nums[j]) * rightMax[j]);
            leftMax = Math.max(leftMax, nums[j]);
        }
        return ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

方法三：一次遍历

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public long maximumTripletValue(int[] nums) {
        long ans = 0;
        int maxDiff = 0, leftMax = 0;
        for (int x : nums) {
            ans = Math.max(ans, (long) maxDiff * x);
            maxDiff = Math.max(maxDiff, leftMax - x);
            leftMax = Math.max(leftMax, x);
        }
        return ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$