【力扣刷题】Leetcode 2592 最大化数组的伟大值

1. Leetcode 2592 最大化数组的伟大值

• 题目链接
  
  
  

• 本题思考的关键点：
  ① nums 的最小值要参与匹配，否则更大的数字更难匹配上；
  ② nums 最小值要与次小值进行比较，这样才能贡献值最大；
  
  

• 用双指针的思想解题
  ① 双指针的模板
  
  
• 本题双指针代码如下：

	int cnt = 0;
    for (int i = 0, j = 0; j < n; i ++)
    {
        while (j < n && nums[i] == nums[j])  j ++;

        if (j >= n) break;

        if (nums[j] > nums[i])
        {
            cnt ++;
            j ++;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

• 上面这段双指针的代码简化如下:
  优化抓住的条件：1. 从大的数据进行枚举，因为从题目可得知，最小值一定要参匹配；

    int cnt = 0;
    for (int i = 0; i < nums.size(); i ++)
        if (nums[cnt] < nums[i])
            cnt ++;
1
2
3
4

• 用二分的思想解题
  ② 双指针的模板
  
  
• 本题二分答案代码如下：

class Solution {
public:

    int maximizeGreatness(vector<int>& nums) {

    sort(nums.begin(), nums.end());  

    // 二分答案
    int l = 0, r = nums.size();
    while (l < r)
    {
        int mid = (l + r + 1) / 2;

        if (check(nums, mid))
            l = mid;
        else 
            r = mid - 1;
    }
    return l;
}

    bool check(vector<int>& nums, int k)
    {
        int n = nums.size();

        for (int i = 0; i < k; i ++)
            if (nums[i] >= nums[n - k + i])
                return false;

        return true;
    }
};
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