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

Posted on In Views:

1，问题描述

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

难度：中等

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

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

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

示例 1：

1
2
3
4
输入：nums = [12,6,1,2,7]
输出：77
解释：下标三元组 (0, 2, 4) 的值是 (nums[0] - nums[2]) * nums[4] = 77 。
可以证明不存在值大于 77 的有序下标三元组。

示例 2：

1
2
3
4
输入：nums = [1,10,3,4,19]
输出：133
解释：下标三元组 (1, 2, 4) 的值是 (nums[1] - nums[2]) * nums[4] = 133 。
可以证明不存在值大于 133 的有序下标三元组。

示例 3：

1
2
3
输入：nums = [1,2,3]
输出：0
解释：唯一的下标三元组 (0, 1, 2) 的值是一个负数，(nums[0] - nums[1]) * nums[2] = -3 。因此，答案是 0 。

提示：

  • 3 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6

2，初步思考

​ 解法1:暴力求解

​ 时间复杂度O（n^3），空间复杂度O（1）

​ 解法2:优先确定一个值，找到另外两个值

​ 时间复杂度O（n^2），空间复杂度O（1）

​ 解法3:最大前缀、最大后缀数组

​ 时间复杂度O（n），空间复杂度O（n）

​ 解法4:贪心算法

​ 时间复杂度O（n），空间复杂度O（1）

3，代码处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
package days;

import support.Pair;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class _2873有序三元组中的最大值I {

    // 贪心算法
    public long maximumTripletValue_greedy(int[] nums) {
        int n = nums.length;
        long res = 0;
        long imax = 0;// i的最大值
        long dmax = 0;// nums[i]-nums[j]的最大值
        for (int i = 0; i < n; i++) {
            res = Math.max(res, (long) dmax * (long) nums[i]);
            dmax = Math.max(dmax, imax - nums[i]);
            imax = Math.max(imax, nums[i]);
        }
        return res;
    }

    public long maximumTripletValue_pre_suffix_optimize(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][2];
        dp[0][0] = nums[0];
        dp[n - 1][1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            dp[i][1] = Math.max(nums[i], dp[i + 1][1]);
        }
        long res = 0;
        for (int i = 1; i < n - 1; i++) {
            res = Math.max(res, (long) (dp[i - 1][0] - nums[i]) * (long) dp[i + 1][1]);
            dp[i][0] = Math.max(nums[i], dp[i - 1][0]);
        }
        return res;
    }

    // 前缀后缀最大值
    // 时间复杂度：O(n)，空间复杂度：O(n)
    public long maximumTripletValue_pre_suffix(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][2];
        dp[0][0] = nums[0];
        dp[n - 1][1] = nums[n - 1];
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(nums[i], dp[i - 1][0]);
        }
        for (int i = n - 2; i >= 0; i--) {
            dp[i][1] = Math.max(nums[i], dp[i + 1][1]);
        }
        long res = 0;
        for (int i = 1; i < n - 1; i++) {
            res = Math.max(res, (long) (dp[i - 1][0] - nums[i]) * (long) dp[i + 1][1]);
        }
        return res;
    }


    // 暴力求解法(找到最小值，向两边扩散)
    // 时间复杂度为O(n^2)，空间复杂度：O(1)
    public long maximumTripletValue_brute(int[] nums) {
        int n = nums.length;
        if (n < 3) return 0;
        PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(Comparator.comparingInt(Pair::getValue));
        for (int i = 1; i < n - 1; i++) {
            pq.add(new Pair<>(i, nums[i]));
        }

        long res = 0;
        while (!pq.isEmpty()) {
            Pair<Integer, Integer> poll = pq.poll();
            int maxLeft = nums[0];
            int maxRight = nums[n - 1];
            for (int i = 1; i < poll.getKey(); i++) {
                if (nums[i] > maxLeft) maxLeft = nums[i];
            }
            for (int i = poll.getKey() + 1; i < n; i++) {
                if (nums[i] > maxRight) maxRight = nums[i];
            }
            long cur = (long) (maxLeft - poll.getValue()) * (long) maxRight;
            res = Math.max(res, cur);
        }
        return res;
    }


    // 模式识别，找出最小值，分左右两边
    public long maximumTripletValue_fail(int[] nums) {
        if (nums.length < 3) return 0;
        int n = nums.length;
        int min = nums[1];
        int minIdx = 1;
        for (int i = 1; i < n - 1; i++) {
            if (nums[i] < min) {
                min = nums[i];
                minIdx = i;
            }
        }
        int maxLeft = nums[0];
        int maxLeftIdx = 0;
        for (int i = 1; i < minIdx; i++) {
            if (nums[i] > maxLeft) {
                maxLeft = nums[i];
                maxLeftIdx = i;
            }
        }

        int maxRight = nums[n - 1];
        int maxRightIdx = n - 1;
        for (int i = minIdx + 1; i < n; i++) {
            if (nums[i] > maxRight) {
                maxRight = nums[i];
                maxRightIdx = i;
            }
        }
        long cur = (long) (maxLeft - min) * (long) maxRight;
        long left = maximumTripletValue_greedy(Arrays.copyOfRange(nums, 0, minIdx));
        long right = maximumTripletValue_greedy(Arrays.copyOfRange(nums, minIdx + 1, n));
        cur = Math.max(cur, Math.max(left, right));
        return cur < 0 ? 0 : cur;
    }

    public static void main(String[] args) {
        _2873有序三元组中的最大值I threeSum = new _2873有序三元组中的最大值I();
//        System.out.println(threeSum.maximumTripletValue(new int[]{6, 3, 4, 6, 3, 4, 5}));
//        System.out.println(threeSum.maximumTripletValue(new int[]{12, 6, 1, 2, 7}));
//        System.out.println(threeSum.maximumTripletValue(new int[]{1, 10, 3, 4, 19}));
//        System.out.println(threeSum.maximumTripletValue(new int[]{1, 2, 3}));
        System.out.println(threeSum.maximumTripletValue_greedy(new int[]{8, 6, 3, 13, 2, 12, 19, 5, 19, 6, 10, 11, 9}));
    }
}
/**
 * 2，10，10，10，5，1，1000
 * 8,6,3,13, 2 ,12,19,5,19,6,10,11,9 = （13-2）* 19= 11 *19 = 219
 */