贪心算法解题思路与实战

MrHe··4 min read

贪心算法是我特别喜欢的一种算法思想，它不像动态规划那样需要考虑所有情况，也不像回溯算法那样需要不断尝试。贪心算法的核心就是在每一步都做出当前看起来最优的选择，希望能够得到全局最优解。

今天我来分享几个经典的贪心算法问题，从基础到进阶，展示不同的思考角度。

分发饼干问题

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j]。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i，这个孩子会得到满足。目标是尽可能满足越多的孩子越好，并输出最大满足孩子数。

解法一：排序 + 双指针（贪心）

最容易想到的思路是：把最大的饼干分给胃口最大的孩子。这样能避免"大材小用"的情况。

public int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g);
    Arrays.sort(s);

    int child = g.length - 1;
    int cookie = s.length - 1;
    int count = 0;

    while (child >= 0 && cookie >= 0) {
        if (s[cookie] >= g[child]) {
            count++;
            child--;
            cookie--;
        } else {
            child--;
        }
    }

    return count;
}

解法二：排序 + 单指针（贪心）

另一种贪心思路是：用最小的饼干满足最小胃口的孩子。这样能保留大的饼干给胃口大的孩子。

public int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g);
    Arrays.sort(s);

    int child = 0;
    int cookie = 0;
    int count = 0;

    while (child < g.length && cookie < s.length) {
        if (s[cookie] >= g[child]) {
            count++;
            child++;
            cookie++;
        } else {
            cookie++;
        }
    }

    return count;
}

解法三：不排序的哈希表解法

虽然这个解法效率不一定高，但它提供了另一种思考角度：

public int findContentChildren(int[] g, int[] s) {
    Map<Integer, Integer> cookieMap = new HashMap<>();
    for (int size : s) {
        cookieMap.put(size, cookieMap.getOrDefault(size, 0) + 1);
    }

    int count = 0;
    Arrays.sort(g);

    for (int greed : g) {
        for (int size = greed; size <= 1000; size++) {
            if (cookieMap.containsKey(size) && cookieMap.get(size) > 0) {
                count++;
                cookieMap.put(size, cookieMap.get(size) - 1);
                break;
            }
        }
    }

    return count;
}

摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。可以通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

解法一：贪心（统计峰谷值）

摆动序列的规律就是峰谷交替出现。我们只需要统计这些峰和谷的数量。

public int wiggleMaxLength(int[] nums) {
    if (nums.length <= 1) {
        return nums.length;
    }

    int count = 1;
    int prevDiff = 0;

    for (int i = 1; i < nums.length; i++) {
        int diff = nums[i] - nums[i-1];
        if ((diff > 0 && prevDiff <= 0) || (diff < 0 && prevDiff >= 0)) {
            count++;
            prevDiff = diff;
        }
    }

    return count;
}

解法二：动态规划

这道题也可以用动态规划来解决：

public int wiggleMaxLength(int[] nums) {
    if (nums.length <= 1) {
        return nums.length;
    }

    int[] up = new int[nums.length];
    int[] down = new int[nums.length];
    up[0] = 1;
    down[0] = 1;

    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i-1]) {
            up[i] = down[i-1] + 1;
            down[i] = down[i-1];
        } else if (nums[i] < nums[i-1]) {
            down[i] = up[i-1] + 1;
            up[i] = up[i-1];
        } else {
            up[i] = up[i-1];
            down[i] = down[i-1];
        }
    }

    return Math.max(up[nums.length-1], down[nums.length-1]);
}

解法三：优化空间的动态规划

我们可以观察到，当前状态只依赖于前一个状态，所以可以优化空间：

public int wiggleMaxLength(int[] nums) {
    if (nums.length <= 1) {
        return nums.length;
    }

    int up = 1, down = 1;

    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i-1]) {
            up = down + 1;
        } else if (nums[i] < nums[i-1]) {
            down = up + 1;
        }
    }

    return Math.max(up, down);
}

最大子数组和

给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

解法一：贪心算法

这是最经典的贪心解法，当当前子数组和小于0时，就重新开始。

public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int maxSum = nums[0];
    int curSum = nums[0];

    for (int i = 1; i < nums.length; i++) {
        if (curSum < 0) {
            curSum = nums[i];
        } else {
            curSum += nums[i];
        }

        maxSum = Math.max(maxSum, curSum);
    }

    return maxSum;
}

解法二：动态规划

这也是典型的动态规划应用：

public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    int maxSum = nums[0];

    for (int i = 1; i < nums.length; i++) {
        dp[i] = Math.max(nums[i], dp[i-1] + nums[i]);
        maxSum = Math.max(maxSum, dp[i]);
    }

    return maxSum;
}

解法三：分治法

这道题也可以用分治思想来解决：

public int maxSubArray(int[] nums) {
    return divideConquer(nums, 0, nums.length - 1);
}

private int divideConquer(int[] nums, int left, int right) {
    if (left == right) {
        return nums[left];
    }

    int mid = left + (right - left) / 2;

    int leftMax = divideConquer(nums, left, mid);
    int rightMax = divideConquer(nums, mid + 1, right);

    // 计算跨越中间点的最大子数组和
    int leftBorderMax = Integer.MIN_VALUE;
    int rightBorderMax = Integer.MIN_VALUE;
    int sum = 0;

    for (int i = mid; i >= left; i--) {
        sum += nums[i];
        leftBorderMax = Math.max(leftBorderMax, sum);
    }

    sum = 0;
    for (int i = mid + 1; i <= right; i++) {
        sum += nums[i];
        rightBorderMax = Math.max(rightBorderMax, sum);
    }

    int crossMax = leftBorderMax + rightBorderMax;

    return Math.max(Math.max(leftMax, rightMax), crossMax);
}

贪心算法解题思路总结

通过以上例子，我想分享几个贪心算法的解题思路：

  1. 排序优先：贪心算法往往与排序搭配使用，如分发饼干问题。排序可以帮助我们更容易地做出局部最优选择。

  2. 寻找规律：摆动序列问题中，我们需要观察峰谷交替的规律，而不是盲目地尝试各种可能性。

  3. 局部最优：最大子数组和问题中，我们只关注当前子数组和是否为负，如果是，就重新开始。这就是局部最优选择。

  4. 验证贪心选择性质：在使用贪心算法前，需要确保局部最优选择能导致全局最优解。如果不行，可能需要考虑动态规划等其他方法。

  5. 多种思路对比：一个问题往往有多种解法，通过对比不同解法，可以更好地理解问题的本质。

  • #6lsq5bd566x5rov