贪心算法入门（二）

相关文章

贪心算法入门（一）-CSDN博客

1.什么是贪心算法？

        贪心算法是一种解决问题的策略，它将复杂的问题分解为若干个步骤，并在每一步都选择当前最优的解决方案，最终希望能得到全局最优解。这种策略的核心在于“最优”二字，意味着我们追求的是以最少的时间和精力，快速获得正确的结果。

        然而，“希望得到全局最优解”就表示贪心算法并不意味着一定能得到全局最优解。实际上，并不是所有问题都可以通过贪心策略解决。为了确保贪心策略的有效性，需要对其进行严格的证明。而且，不同的问题往往需要采用不同的贪心策略。

        如果你觉得这一点仍然比较抽象，接下来我将通过五道具体的例题来详细说明贪心算法的应用及其背后的思路。

2.递增的三元子序列

334. 递增的三元子序列 - 力扣（LeetCode）

这道题跟在贪心算法入门（一）中的最长递增子序列的思路是一样的。在最长递增子序列中使用了贪心加二分的策略。

回顾一下上题的贪心策略：选用链表接收子序列。依次检索数组中的每个值，如果扫描的值大于链表中的最后一个值则添加到链表末尾，如果小于则用二分寻找合适的位置插入，插入的位置要严格保证大于链表左边的值。最后返回链表的大小，就是最长递增子序列的长度。

而该题已经确定了最长递增子序列的长度，只需要判断在数组中是否存在这样的三元递增子序列即可，所以可以省略用链表表示变量，用两个int型变量a,b表示三元连续递增的第一个位置和第二个位置代替，如果检索到某个值大于b时直接返回true。

注意a,b的初始化，a的初始化就是数组下标0的值，b的值可以初始化为一个最大值。

2.1 代码实现

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        int a  = nums[0], b = Integer.MAX_VALUE;
        for(int i = 1; i < n; i++){
            if(nums[i] > b) return true;
            else if(nums[i] > a) b = nums[i];
            else a = nums[i];
        }
        return false;
    }
}

该题把值插入到正确位置使用了两个条件判断，如果大于第二个位置b的值说明改值可以接在b后面组成三元递增序列，所以这里就知道为什么要把b初始化为最大值了。如果第一个条件不成立则判断是否大于a，如果成立则说明a < x <= b，则把b更新为x,否则说明x比a第一个位置的还小，更新a位置的值。

3.最长连续递增序列

674. 最长连续递增序列 - 力扣（LeetCode）

 从给出的示例1看，这道题跟最长递增子序列的区别就是找出的递增序列是不能被间隔的。

那么这道题同样也可以用上道题的思路做，但是不用这么麻烦，因为这道题的要求更简单。

从下标为1的位置开始检索，判断是否大于前一个位置的数，如果满足则是递增的，此时len加1(len表示最长递增子序列的长度，初始化为1，因为单独的一个数也可以看成一个递增子序列），直到扫描的位置不满足大于前一个位置为止，更新ret为ret和len的较大值。这时无需再跳回去以第一个位置为起点计算，因为前面扫描过的位置中无论以哪个位置为起点的最长连续递增自序列的长度都不会超过刚刚的计算出的len值。

3.1 代码实现

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int ret = 1, tmp = 1;
        for(int i = 1; i < nums.length; i++){
            if(nums[i] > nums[i - 1]) tmp++;
            else tmp = 1;
            ret = Math.max(ret,tmp);
        }
        return ret;
    }
}

4.买卖股票的最佳时机

121. 买卖股票的最佳时机 - 力扣（LeetCode）

理解题目： 选择一天买入股票，再选择一天卖出股票，买入肯定要在卖出之前（对应数组下标前后关系），且要利润最大，就说明希望以选择买入的值最小，选择卖出的最大。

这道题跟递增序列的思路也很像，我们只需一次扫描数组，找到所有的二元递增序列，并找到差值最大的那个就是答案了。只不过这道题每次更新的结果值不是长度，而是a,b之间的差值。

4.1 代码实现

class Solution {
    public int maxProfit(int[] prices) {
        int ret = 0, a = prices[0];
        for(int x : prices){
            if(x > a) ret = Math.max(ret, x - a);
            else a = x;
        }
        return ret;
    }
}

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

122. 买卖股票的最佳时机 II - 力扣（LeetCode）

该题与上一题的区别就是不限制你买入的次数和卖出的次数，所以可以进行多次交易，然后求最大利润。

这道题的思路相比1会更简单，因为我们只需把所有上升的部分相加起来就是最大利润。数组我们可以把它映射到折线图中：

5.1 代码实现

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

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

1005. K 次取反后最大化的数组和 - 力扣（LeetCode）

这道题的思路也很简单，要最后的和最大，首先尽量把数组中原本的负数取反变为正数，如果k小于等于数组中原本的负数个数，那么让这些负数全部取反为正即和最大。如果还有剩余次数，此时数组中都是非负整数了，如果剩余次数为偶数则可以维持不变，如果为奇数就说明要选取一个最小的非负整数取反才能最大。

6.1 代码实现

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        int min = 200, m = 0, sum = 0;
        for(int x : nums){
            if(x  < 0) m++;
            min = Math.min(min, Math.abs(x));
        }
        if(m > k){ 
            Arrays.sort(nums);
            for(int i = 0; i < k; i++) sum += -nums[i];
            for(int i = k; i < nums.length; i++) sum += nums[i];
        }else{
            for(int i = 0; i < nums.length; i++) sum += Math.abs(nums[i]);
            if((k - m) % 2 == 1) sum -= 2 * min;
        }
        return sum;
    }
}

 该题使用了一些优化，当负数个数大于k的时候才需要使用Arrays.sort(nums);进行排序，将负数归到最前，然后计算结果值。如果负数小于k的时候就无需sort，直接用Math.abs(nums[i]);函数将数组中的值相加，最后再判断剩余次数的奇偶性进行后续操作。