算法沉淀——贪心算法三（leetcode真题剖析）

算法沉淀——贪心算法三

• 01.买卖股票的最佳时机 II
• 02.K 次取反后最大化的数组和
• 03.按身高排序
• 04.优势洗牌

01.买卖股票的最佳时机 II

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     总利润为 4 + 3 = 7 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     总利润为 4 。

示例 3：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。 

提示：

• 1 <= prices.length <= 3 * 104
• 0 <= prices[i] <= 104

思路

通过画图我们不难看出上升区域利润如果都拿到手即为最大利润，这里有两种写法，一种是一次性加上一整段上升区域，另一种是计算每一小段上升区域

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ret=0,n=prices.size();
        for(int i=0;i<n;i++){
            int j=i;
            while(j+1<n&&prices[j+1]>prices[j]) j++;
            ret+=prices[j]-prices[i];
            i=j;
        }
        return ret;
    }
};



class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ret=0,n=prices.size();
        for(int i=1;i<n;i++){
            if(prices[i]>prices[i-1]) 
                ret+=prices[i]-prices[i-1];
        }
        return ret;
    }
};

02.K 次取反后最大化的数组和

题目链接：https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

• 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。

重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

示例 1：

输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。

示例 2：

输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。

示例 3：

输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。 

提示：

• 1 <= nums.length <= 104
• -100 <= nums[i] <= 100
• 1 <= k <= 104

思路

这里我们需要分情况讨论，设整个数组中负数的个数为m个：

1、m>k：把前k小的负数全变成正数
2、m==k：把所有的负数全变成正数；
3、m<k：先把负数变成正数；然后根据k-m的奇偶情况分情况讨论

代码

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int m=0,mini=INT_MAX,n=nums.size();
        for(auto x:nums){
            if(x<0) m++;
            mini=min(mini,abs(x));
        }

        int ret=0;
        if(m>k){
            sort(nums.begin(),nums.end());
            for(int i=0;i<k;i++) ret+=-nums[i];
            for(int i=k;i<n;i++) ret+=nums[i]; 
        }
        else{
            for(auto x:nums) ret+=abs(x);
            if((k-m)%2) ret-=mini*2;
        }
        return ret;
    }
};

03.按身高排序

题目链接：https://leetcode.cn/problems/sort-the-people/

给定一个字符串数组names和一个由不同正整数heights组成的数组。两个数组的长度都是n

对于每个索引i，names[i]和heights[i]表示该人的姓名和身高。

返回按人物身高降序names排序。

示例1：

输入： names = ["Mary","John","Emma"], heights = [180,165,170]
输出： ["Mary","Emma","John"]
解释： Mary 最高，其次是 Emma 和 John 。

示例2：

输入： names = ["Alice","Bob","Bob"], heights = [155,185,150]
输出： ["Bob","Alice","Bob"]
解释：第一个 Bob 最高，其次是 Alice和第二个鲍勃。

限制条件：

• n == names.length == heights.length
• 1 <= n <= 103
• 1 <= names[i].length <= 20
• 1 <= heights[i] <= 105
• names[i]由小写和大写英文字母组成。
• 的所有值heights都是不同的。

思路

这道题目并不是一道贪心题，但是可以为下一道贪心题提供思路，这里我们额外建立一个下标数组，相对于身高对下标数组进行排序，最后映射名字输出即可。

代码

class Solution {
public:
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        int n=names.size();
        vector<int> index(n);
        for(int i=0;i<n;i++) index[i]=i;

        sort(index.begin(),index.end(),[&](int i,int j){return heights[i]>heights[j];});

        vector<string> ret;
        for(int i:index) ret.push_back(names[i]);

        return ret;
    }
};

04.优势洗牌

题目链接：https://leetcode.cn/problems/advantage-shuffle/

给定两个长度相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。

返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。

示例 1：

输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]
输出：[2,11,7,15]

示例 2：

输入：nums1 = [12,24,8,32], nums2 = [13,25,32,11]
输出：[24,32,8,12]

提示：

• 1 <= nums1.length <= 105
• nums2.length == nums1.length
• 0 <= nums1[i], nums2[i] <= 109

思路

当己方此时最差的比不过对面最差的时候，让我方最差的去处理掉对面最好的（反正要输，不如去拖掉对面⼀个最强的）；
当己方此时最差的能比得上对面最差的时候，就让两者比对下去（最差的都能获胜，为什么要输呢）。
每次决策，都会使我方处于优势

代码

class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        int n=nums1.size();
        sort(nums1.begin(),nums1.end());
        vector<int> index(n);
        for(int i=0;i<n;i++) index[i]=i;
        sort(index.begin(),index.end(),[&](int i,int j){return nums2[i]<nums2[j];});

        vector<int> ret(n);
        int left=0,right=n-1;
        for(auto x:nums1){
            if(x>nums2[index[left]]) ret[index[left++]]=x;
            else ret[index[right--]]=x;
        }

        return ret;
    }
};