Leetcode 71 买卖股票的最佳时机 | 增量元素之间的最大差值

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

121. 买卖股票的最佳时机

给定一个数组，其中第 i 个元素表示某支股票在第 i 天的价格。

你被允许进行至多一次交易：即选择一天买入，之后的某一天卖出（必须是不同的日期）。目标是设计一种算法，计算出能够获得的最大利润。

如果无法盈利，则返回 0。函数应返回整个过程中可获取的最大利润值。

示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天以价格 1 买入，在第 5 天以价格 6 卖出，利润为 6 - 1 = 5。注意不能在买入前卖出，且卖出价必须高于买入价。

示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：价格持续下跌，无法完成任何盈利交易，因此最大利润为 0。

prices

i

prices[i]

1 <= prices.length <= 105

0 <= prices[i] <= 104

代码实现与问题分析

当前实现存在运行错误，虽然可以通过部分测试用例，但整体逻辑存在问题。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0){
            return 0 ;
        }
        int maxPro = 0 ;
        int minP = prices[0];

        for (int i = 0 ; i < n ; i ++){
            int curPro = prices[i] - minP;
            maxPro = max (maxPro ,curPro);
            minP = min( minP, prices[i]);
        }

        return maxPro;
    }
};

原始代码的问题表现为：部分用例通过，但执行时报错或结果不正确。

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

一、主要问题：数组越界访问

在内层循环中出现了非法下标访问：

for (int j = n ; j > i ; j--) {
    curPro = prices[j] - prices[i] ; // 致命错误：j初始值为n，超出数组范围
}

数组 prices 的有效索引范围是 0 到 n-1（n 为数组长度）；当 j 等于 n 时，prices[j] 实际上访问了超出边界的内存位置，导致程序崩溃。

例如，当 j = n 时，prices[j] 并不存在 —— 这正是「数组越界」错误的根本原因。

即使将该处修正为 j < n，双重循环的时间复杂度仍为 O(n)，面对大规模输入（如 n 接近 10）会超时。

prices

0 ~ n-1

n = prices.size()

j = n

prices[j]

j = n-1

O(n?)

二、次要缺陷：逻辑冗余无效判断

如下语句中的三元操作并未产生实际影响：

curPro > 0 ? curPro : 0 ; // 这行代码没有任何效果！

由于判断结果未赋值给任何变量，等同于空操作，属于无意义代码。正确的写法应当是将其结果用于更新 maxProfit：

curPro = curPro > 0 ? curPro : 0; // 或者 curPro = max(curPro, 0);

curPro

三、优化解法：单次遍历策略（O(n) 时间复杂度）

解决此类“最佳买卖时机”问题的最优思路是：

• 遍历数组的同时维护一个历史最低价格；
• 对于每一天的价格，计算其与当前最小价格的差值；
• 不断更新所能达到的最大利润。

这种方法仅需一次扫描即可完成，时间效率显著提升。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0; // 空数组直接返回0
        
        int minPrice = prices[0]; // 记录遍历到当前的最小价格
        int maxPro = 0;           // 记录最大利润
        
        for (int i = 1; i < prices.size(); ++i) {
            // 计算当前卖出能获得的利润
            int curPro = prices[i] - minPrice;
            // 更新最大利润（利润为负则取0）
            maxPro = max(maxPro, curPro);
            // 更新最小价格（如果当前价格更低）
            minPrice = min(minPrice, prices[i]);
        }
        
        return maxPro;
    }
};

四、原方案其他不足之处

即便修复了下标越界问题（将 j <= n 改为 j < n），仍然存在以下缺陷：

• 时间复杂度过高：嵌套循环在处理大尺寸数据集时极易超时；
• 重复计算严重：从后往前遍历并无必要，造成大量无效比较；
• 边界情况处理模糊：若输入为空数组，虽然某些情况下能侥幸返回 0，但仍建议显式判断并处理空输入情形。

j = n

j = n-1

n=0

五、测试对比验证

测试用例	原始代码（修正前）	原始代码（修正后）	最优解法
[7,1,5,3,6,4]	崩溃（越界）	5（正确）	5
[7,6,4,3,1]	崩溃（越界）	0（正确）	0
[]	0（侥幸正确）	0（正确）	0
[1,2]	崩溃（越界）	1（正确）	1
包含 10 个元素的大数组	崩溃 / 超时	超时	快速通过

综上所述，原代码失败的核心原因是数组越界访问，即使修复此问题，也因时间复杂度偏高而无法应对极端用例。推荐采用线性时间复杂度的一次遍历方法来实现稳定高效的解决方案。

2016. 增量元素之间的最大差值

给定一个下标从 0 开始的整数数组 nums，其长度为 n。要求找出满足条件的所有数对 (i, j) 中的最大差值 nums[j] - nums[i]，其中 i < j 且 nums[i] < nums[j]。

若不存在符合条件的数对，则返回 -1。

示例 1：
输入：nums = [7,1,5,4]
输出：4
解释：当 i = 1, j = 2 时，nums[j] - nums[i] = 5 - 1 = 4。尽管 7 - 1 = 6 更大，但由于 i > j 不符合要求，故不可取。

示例 2：
输入：nums = [9,4,3,2]
输出：-1
解释：没有满足 i < j 且 nums[i] < nums[j] 的组合，因此返回 -1。

示例 3：
输入：nums = [1,5,2,10]
输出：9
解释：最大差值出现在 i = 0, j = 3，对应差值为 10 - 1 = 9。

nums

n

nums[j] - nums[i]

0 <= i < j < n

nums[i] < nums[j]

j

-1

n == nums.length

2 <= n <= 1000

1 <= nums[i] <= 109

代码实现与错误剖析

当前提交版本存在问题，以下是详细分析过程。

class Solution {
public:
    int maximumDifference(vector<int>& nums) {
        int n = nums.size();
        if (n < 2 ){
            return -1 ;
        }
        int minNum = nums[0];
        int maxDiff = -1 ;
        for (int i = 1; i < n ; i ++){
            minNum = min (minNum , nums[i - 1]);
            int diff = nums[i] - minNum ;
            if (diff > 0 ){
            maxDiff = max(maxDiff,diff);
            }
        }
        return maxDiff;
    }
};

承认编码失误：“错错错，是我的错！”

class Solution {
public:
    int maximumDifference(vector<int>& nums) {
        int n = nums.size();
        if (n < 3 ){
            return -1 ;
        }
        int minNum = nums[0];
        int maxDiff = -1 ;
        for (int i = 0; i < n ; i ++){
            int diff = nums[i] - minNum ;
            maxDiff = max(maxDiff,diff);
            minNum = min(minNum , nums[i]);
        }
        return maxDiff;
    }
};

第一步：明确题目核心约束

本题（LeetCode 第 2016 题）的关键规则如下：

• 寻找两个索引 i 和 j，使得 i < j 且 nums[i] < nums[j]；
• 在此基础上使 nums[j] - nums[i] 最大化；
• 若无满足条件的数对，返回 -1。

maximumDifference

nums[j] - nums[i]

i < j

nums[j] > nums[i]

-1

第二步：三大核心错误解析

现有代码存在三个关键性错误：

1. 未正确维护前置最小值，导致无法准确追踪可配对的最小元素；
2. 差值更新逻辑错误，可能在 nums[i] ≥ nums[j] 的情况下仍进行更新；
3. 未能正确处理无有效数对的情形，返回值不符合规范。

这些问题共同导致输出结果偏离预期。

错误 1：不正确的边界条件处理（当 n < 3 时返回 -1）

题目中明确指出，只要数组长度大于等于 2，就可能存在满足 i < j 的合法数对。例如，输入

[1,2]

时，正确结果应为 1。然而，在你的代码实现中，使用了 n < 3 则返回 -1 的判断逻辑

n < 3

，这会错误地排除掉长度为 2 的有效情况

if (n < 3 ){ return -1 ; } // 错误！正确应该是 n < 2 才返回-1（甚至n=2也能判断）

，导致结果出错。

错误 2：逻辑执行顺序不当（先计算差值后更新最小值）

当前代码的处理流程是：先用当前元素与已记录的最小值 minNum 计算差值，之后才更新 minNum。这种顺序会导致问题 —— 当遇到一个与 minNum 相等的元素时

i=0

，差值为 0

diff = nums[0] - minNum（nums[0]）= 0

，程序可能将结果从 -1 更新为 0

maxDiff

。但根据题意要求，合法差值必须严格大于 0

nums[j] > nums[i]

，因此 0 不符合要求。更严重的是，若数组为

[5,4,3,2,1]

这样的情况，代码将输出 0 而非正确的 -1，明显违背题目规定。

正确的处理方式应是：先更新 minNum（确保其代表当前位置之前的所有元素中的最小值），再基于该最小值计算当前元素的差值，并仅保留大于 0 的结果。

错误 3：未对非正差值进行过滤

即使调整了逻辑顺序，若输入数组为严格递减序列，如

[5,4,3]

，所有相邻或跨位的差值都将小于等于 0。此时，算法应当返回 -1 表示无合法解。但原代码未设置对 ≤0 差值的有效过滤机制，可能导致保留无效的 0 或负数作为结果，造成错误输出。

修正后的代码逻辑如下：

class Solution {
public:
    int maximumDifference(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) { // 错误1：修正边界条件（长度<2才无意义）
            return -1;
        }
        int minNum = nums[0]; // 初始最小值为第一个元素
        int maxDiff = -1;     // 初始最大差值为-1（无合法数对时返回）
        
        // 从第二个元素开始遍历（i=1，保证i>0，即j>i）
        for (int i = 1; i < n; ++i) {
            // 错误2：先更新最小值（minNum是i之前的数，保证i<j）
            minNum = min(minNum, nums[i-1]);
            // 计算当前数与minNum的差值，且只保留>0的情况
            int diff = nums[i] - minNum;
            if (diff > 0) { // 错误3：过滤≤0的差值
                maxDiff = max(maxDiff, diff);
            }
        }
        return maxDiff;
    }
};

测试用例对比验证：

输入数组	错误代码输出	修正代码输出	正确结果
[1,2]	-1	1	1
[5,4,3,2,1]	-1	-1	-1
[7,1,5,4]	4	4	4
[9,4,3,2]	-1	-1	-1

核心要点总结：

• 边界条件处理：数组长度 ≥ 2 即可存在合法数对，不应限制为 ≥3；
• 逻辑顺序调整：必须先更新“当前元素之前”的最小值，再计算差值，以保证

  i<j

  的正确性；
• 差值合法性筛选：只保留差值 > 0 的情况，若最终无任何合法差值，则统一返回 -1。

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：code EETC ODE TCO Lee

相关内容：LeetCode股票买卖