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

题目描述

题目思路

两种解法:

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快一些;

第二点是,

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

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

/**
 * @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)