贪心算法LeetCode实战：股票交易、跳跃游戏与数组取反问题解析

贪心算法在解决最优化问题时，常常能提供清晰高效的思路。本文通过四道经典的LeetCode题目，深入剖析如何运用局部最优策略来达到全局最优解。

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

题目描述
给定一个数组 prices，其中 prices[i] 表示某支股票第 i 天的价格。你可以完成多笔交易（多次买卖同一支股票），但不能同时参与多笔交易（即在再次购买前必须出售掉之前的股票）。请计算你所能获取的最大利润。

示例

• 输入: [7,1,5,3,6,4]
• 输出: 7
• 解释: 在第 2 天（价格=1）买入，第 3 天（价格=5）卖出，利润 4。随后在第 4 天（价格=3）买入，第 5 天（价格=6）卖出，利润 3。总利润 4+3=7。

思路解析
本题的核心在于理解：最终的最大利润可以分解为每日的利润之和。例如，从第0天买入，第3天卖出，利润为 prices[3] - prices[0]，这等价于 (prices[3]-prices[2]) + (prices[2]-prices[1]) + (prices[1]-prices[0])。

因此，我们只需计算每天的利润（今天价格减昨天价格），并收集所有正的利润进行累加，即可得到最大总利润。贪心策略体现在：只要今天比昨天价格高，就认为这笔“当日交易”可以产生利润。

下图清晰地展示了这一分解过程：

图解：将总利润分解为每日的正利润之和。

代码实现 (TypeScript)

function maxProfit(prices: number[]): number {
    let res: number = 0;
    for (let i = 1; i < prices.length; i++) {
        // 只收集正利润
        res += Math.max(prices[i] - prices[i - 1], 0);
    }
    return res;
};

55. 跳跃游戏

题目描述
给定一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

示例

• 输入: [2,3,1,1,4]
• 输出: true
• 解释: 从下标 0 跳 1 步到下标 1，再从下标 1 跳 3 步到达最后一个下标。

思路解析
本题的关键不是纠结于具体跳几步，而是关注当前能够覆盖的最远范围。我们维护一个变量 cover，表示当前能跳到的最远下标索引。

在遍历数组时，只要当前位置 i 在 cover 的覆盖范围内，我们就可以从这个位置起跳，并尝试更新 cover 为 max(cover, i + nums[i])。如果 cover 最终能够覆盖或超过最后一个下标，则返回 true。

下图展示了覆盖范围如何决定是否能到达终点：

图解：通过不断更新最大覆盖范围来判断可达性。左图覆盖未及终点，返回false；右图覆盖终点，返回true。

代码实现 (TypeScript)

function canJump(nums: number[]): boolean {
    let farthestIndex: number = 0; // 当前能到达的最远下标
    let cur: number = 0; // 当前遍历下标
    while (cur <= farthestIndex) {
        // 更新能到达的最远下标
        farthestIndex = Math.max(farthestIndex, cur + nums[cur]);
        // 如果已经能覆盖终点，提前返回
        if (farthestIndex >= nums.length - 1) return true;
        cur++;
    }
    // 循环结束仍未覆盖终点
    return false;
};

掌握这类问题的核心，需要扎实的算法与数据结构基础，贪心策略是其中重要的解题范式之一。

45. 跳跃游戏 II

题目描述
给定一个非负整数数组 nums，你最初位于数组的第一个位置。每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。

示例

• 输入: [2,3,1,1,4]
• 输出: 2
• 解释: 从下标 0 跳到下标 1 (跳1步)，然后从下标 1 跳到最后一个下标 (跳3步)。

思路解析
本题是上一题的进阶，要求在可达的前提下，计算最小跳跃次数。贪心策略是：在当前的跳跃覆盖范围内，选择下一次能跳得最远的位置作为起跳点。

我们维护两个关键变量：

1. curFarthestIndex: 当前这一步能覆盖的最远边界。
2. nextFarthestIndex: 下一步能覆盖的最远边界（在curFarthestIndex范围内探索得出）。

当遍历下标 i 移动到 curFarthestIndex 时，说明当前这一步的潜力已经用尽，必须增加一步 (ans++)，并将 curFarthestIndex 更新为 nextFarthestIndex，开始下一轮的探索。注意，为了使逻辑清晰，我们让指针 i 最大遍历到 nums.length - 2 即可。

关键点图解

下图展示了何时需要增加步数（当移动下标到达当前步的最大覆盖边界时）：

图解：移动下标等于当前覆盖最远距离下标，说明需要启动下一步，步数加一。

下图展示了不需要额外增加步数的情况（下一步覆盖范围已直接包含终点）：

图解：移动下标不等于当前覆盖最远距离下标，说明当前覆盖范围已能直接到达终点。

代码实现 (TypeScript)

function jump(nums: number[]): number {
    const length: number = nums.length;
    let curFarthestIndex: number = 0; // 当前跳跃覆盖的最远距离
    let nextFarthestIndex: number = 0; // 下一步跳跃覆盖的最远距离
    let curIndex: number = 0;
    let steps: number = 0;

    // 注意：只需要遍历到倒数第二个元素
    while (curIndex < length - 1) {
        // 更新下一步能跳到的最远位置
        nextFarthestIndex = Math.max(nextFarthestIndex, curIndex + nums[curIndex]);
        // 如果走到了当前这步能到的边界
        if (curIndex === curFarthestIndex) {
            steps++; // 不得不增加一步
            curFarthestIndex = nextFarthestIndex; // 更新当前步的覆盖范围为下一步的
        }
        curIndex++;
    }
    return steps;
};

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

题目描述
给定一个整数数组 nums 和一个整数 k，你可以多次（包括 k 次）选择任意索引 i，将 nums[i] 替换为 -nums[i]。返回数组可能的最大和。

示例

• 输入: nums = [4,2,3], k = 1
• 输出: 5
• 解释: 选择索引 1，数组变为 [4,-2,3]，和为 5。

思路解析
本题运用了两次贪心策略：

1. 局部最优1：为了让和最大，优先翻转绝对值最大的负数（因为负数变正数对和的增益最大）。
2. 局部最优2：如果所有负数都翻转完，k 仍有剩余，此时数组全是非负数。为了使损失最小，应反复翻转当前数组中最小的数（即绝对值最小的数），以消耗剩余的翻转次数。

为了高效实现这两个策略，可以先对数组按绝对值从大到小排序。这样遍历时，先处理绝对值大的负数；翻转完成后，数组末尾的元素就是绝对值最小的元素，便于反复翻转。

代码实现 (TypeScript)

function largestSumAfterKNegations(nums: number[], k: number): number {
    // 1. 按绝对值从大到小排序
    nums.sort((a, b) => Math.abs(b) - Math.abs(a));

    // 2. 贪心1：翻转绝对值最大的负数
    for (let i = 0; i < nums.length && k > 0; i++) {
        if (nums[i] < 0) {
            nums[i] = -nums[i];
            k--;
        }
    }

    // 3. 贪心2：若k还有剩余，反复翻转最小的数（此时已在末尾）
    while (k > 0) {
        nums[nums.length - 1] = -nums[nums.length - 1];
        k--;
    }

    // 4. 求和
    return nums.reduce((pre, cur) => pre + cur, 0);
};

通过以上四道题目的解析，可以看出贪心算法的核心在于在每一步做出当前看起来最优的选择，并期望通过一系列局部最优解最终得到全局最优解。虽然贪心策略并非万能，且证明其正确性有时颇具挑战，但在算法问题中，它往往是通往高效解法的一条捷径。而像“跳跃游戏II”这类题目，则需要更精巧的状态设计和边界处理，是提升算法思维复杂度的优秀练习。