LeetCode——买卖股票的最佳时机(动态规划+更新极值)

简介: LeetCode——买卖股票的最佳时机(动态规划+更新极值)

题目描述

image.png

思路一:更新最大值和最小值

  • 首先,假设第一个元素是价格最小的值minPrice。
  • 定义一个价格最大差maxPriceDiff,并设置值为0。
  • 从数组的第二个元素开始更新价格最大差和最小值。
  • 最小值是在第i个元素和前面的最小值minPrice之间进行比较。
  • 最大价格差则是在前面的最大价格差和(第i天的股票价值-前面的最小值)之间进行比较。
  • 最后返回最大价格差。

AC代码

var maxProfit = function (prices) {
    // 通过不断更新最大值和最小值的方法来求解
    let maxPriceDiff = 0;
    let minPrice = prices[0];
    for (let i = 1; i < prices.length; i++) {
        minPrice = Math.min(prices[i], minPrice);
        let tempMax = Math.max(prices[i] - minPrice);
        maxPriceDiff = Math.max(maxPriceDiff, tempMax);
    }
    return maxPriceDiff;
};
复制代码

思路二:动态规划

详细的思路请看代码中的注释。 需要我们注意的是:本题中只能进行一次交易,例如如果你今天买入那么你手上的现金就是-prices[i]。

dp数组以及下标的含义

  • dp[i][0]:表示第i天,手里不持有股票的现金数
  • dp[i][1]:表示第i天,手里持有股票的现金数

AC代码

var maxProfit = function (prices) {
    // 通过动态规划的方法
    const dp = new Array(prices.length).fill([0, 0]);
    // 设置动态规划的初始值
    // 第0天不持股的情况下,手上的现金数
    dp[0][0] = 0;
    // 第1天持股的情况下,手上的现金数是当日价格的负数
    dp[0][1] = -prices[0];
    // 从第二天开始进行遍历
    for (let i = 1; i < prices.length; i++) {
        // 第i天手上不持股的情况:前一天不持股,或者前一天持股但是今天卖掉了
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        // 第i天手上持股的情况:前一天不持股,今天买入,或者前一天持股今天没卖
        dp[i][1] = Math.max(- prices[i], dp[i - 1][1]);
    }
    // 最终返回的就是最后一天不持股手上的最大现金数
    return dp[prices.length - 1][0]
};
复制代码

题目反思

  • 学会使用动态规划来求解买卖股票的问题
  • 学会通过不断更新最大值和最小值的方法来求解这个问题。
  • 动态规划最重要的是理解dp数组及其下标的含义并准确列出动态规划的方程。
相关文章
|
24天前
|
缓存
力扣每日一题 6/14 动态规划+数组
力扣每日一题 6/14 动态规划+数组
17 1
|
24天前
|
算法 索引
力扣每日一题 6/28 动态规划/数组
力扣每日一题 6/28 动态规划/数组
20 0
|
24天前
|
存储
力扣每日一题 6/19 排序+动态规划
力扣每日一题 6/19 排序+动态规划
11 0
|
24天前
|
算法
力扣每日一题 6/16 字符串 + 随机一题 动态规划/数学
力扣每日一题 6/16 字符串 + 随机一题 动态规划/数学
14 0
|
26天前
|
机器人
【LeetCode】--- 动态规划 集训(二)
【LeetCode】--- 动态规划 集训(二)
17 0
|
26天前
【LeetCode】--- 动态规划 集训(一)
【LeetCode】--- 动态规划 集训(一)
11 0
|
1月前
|
算法
leetcode题解:121.买卖股票的最佳时机
leetcode题解:121.买卖股票的最佳时机
16 0
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(4)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总
|
1月前
|
存储 算法
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(1)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题