Shinkai005

V1

2022/02/12阅读:38主题:红绯

# 【leetcode】121.买卖股票的最佳时机

【leetcode】121.买卖股票的最佳时机.md

image-20220212085245101
image-20220212085245101

题目描述

image-20211229214547399
image-20211229214547399

题目思路

两种解法:

  1. 暴力法
  2. 动态规划

暴力法

因为我们是知道每一天的价格然后 事后 去 思考最大利润;

  1. 我们先找到最小值,
  2. 然后在最小值的右侧找到最大值.
  3. 如果没有那么证明最大利润为0; 因此maxprofit初始值设为0;

动态规划

首先将问题分成多个覆盖的子问题

  1. f(k) 意思是前k天的最大收益

  2. a(k) 当前值,minprice是前k天最小值.

  3. f(k) = a(k) - minprice;

因此我们的任务就是找 前k天的最小值, 不断地找(1-k-1)中的最小值.

个人题解

/**
 * @param {number[]} prices
 * @return {number}
 */

var maxProfit = function(prices{
  /**
  动态规划:用相互重叠的子问题解决问题
  1. f(k) 意思是前k天的最大收益
  2. a(k) 前k天最大值,
  2. f(k) = a(k) - minprice;
     */

        let minprice = Infinity;
        let maxprofit = 0;
        prices.forEach((value)=>{
            minprice  = Math.min(value,minprice);
            maxprofit = Math.max(value-minprice,maxprofit)
        });
        return maxprofit;
    };

暴力解法

/**
 * @param {number[]} prices
 * @return {number}
 */

var maxProfit = function(prices{
  /** 
  暴力解法
  */
    
    let maxprofit = 0;
    for(let i = 0; i<prices.length; i++) {
        for(let j = i+1; j<prices.length;j++){
            if(prices[j]-prices[i]>maxprofit){
                maxprofit = prices[j]-prices[i];
            }
        }
    }
    return maxprofit;
};

总结优化

还是老话, 做题的时候不要太依赖于提供的api, 像是foreach 和 Math.min 方法, 可以用,但是最基础的也要会写.

这样的话,换个语言依旧可以做题.

在leetcode中,用原生速度会比api快一些;

第二点是,

我的动态规划方法,没有做判断, 而是每次都判断大小然后赋值, 从结果上看 确实慢了一些;

image-20211229222917372
image-20211229222917372

前两个是我的,后两个是优化后

image-20211229222949740
image-20211229222949740
/**
 * @param {number[]} prices
 * @return {number}
 */

var maxProfit = function(prices{
  /**
  动态规划:用相互重叠的子问题解决问题
  1. f(k) 意思是前k天的最大收益
  2. a(k) 前k天最大值,
  2. f(k) = a(k) - minprice;
     */

        let minprice = Infinity;
        let maxprofit = 0;
        for (let i = 0; i < prices.length; i++) {
            if (prices[i] < minprice) {
                minprice = prices[i];
            } else if (prices[i] - minprice > maxprofit) {
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    };

时间复杂度(time complexity)

O(n)

空间复杂度(space complexity)

o(1)

分类:

前端

标签:

JavaScript

作者介绍

Shinkai005
V1

公众号:深海笔记Shinkai