贪心算法

买卖股票的最佳时机

简单#121Java时间 O(n)空间 O(1)

题目要做什么

每天有一个股票价格,只能先买入一次,再在之后的某一天卖出一次。求最大利润;无法获利时返回 0。

题目示例输入prices = [7,1,5,3,6,4]
题目示例输出5

01 为什么这样做

扫描每一天,同时记录此前最低买入价。以今天作为卖出日时,最优利润是今天价格减此前最低价。

始终成立的条件

minPrice 是目前见过的最低价格,best 是已经考虑的最大合法利润。

02 看见算法执行

动画与代码同步

修改输入,播放自己的例子

当前使用题目示例
修改输入会改变执行过程;预期输出用于核对结果。
数组 / nums步骤 1
执行状态
本次演示输出播放到最后查看

Solution.java参考解法
1class Solution {2    public int maxProfit(int[] prices) {3        int minPrice = Integer.MAX_VALUE, best = 0;4        for (int price : prices) {5            minPrice = Math.min(minPrice, price);6            best = Math.max(best, price - minPrice);7        }8        return best;9    }10}

键盘控制:A 后退 · D 前进

编程练习

↑↓ 选择↵ 打开Pagefind 全文检索