🚩买卖股票的最好时机(一)

原题传送门

🏳️‍🌈1.题目描述

假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天

2.如果不能获取到任何利润，请返回0

3.假设买入卖出均无手续费

数据范围： 0≤n≤ 10^5 , 0≤val ≤10^4

要求：空间复杂度 O(1)，时间复杂度 O(n)

示例：

输入：

[8,9,2,5,4,7,1]

返回值：

5

说明：

在第3天(股票价格 = 2)的时候买入，在第6天(股票价格 = 7)的时候卖出，最大利润 = 7-2 = 5 ，不能选择在第2天买入，第3天卖出，这样就亏损7了；同时，你也不能在买入前卖出股票。

🏳️‍🌈2.题目分析

由题目描述可知，我们是求给定数组prices 中 prices[j] - prices[i] 的最大值，但是必须保证 j > i

最容易想到暴力法，使用两层循环，并使用一个变量max来记录后面 - 前面的最大值,代码如下：

import java.util.*;
public class Solution {
    /**
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        
        //记录最大值，初始值为0
        int max = 0;
        
        int n = prices.length;
        
            //遍历数组记录所遍历过的价格的最小值  
        for(int i = 0;i < n; i++){
            
          for(int j = i+1; j< n;j++){
              if(prices[j] > prices[i]){
                  max = Math.max(max,prices[j] - prices[i]);
              }
          }
            
        }
        
        return max;
        
    }
}

时间复杂度为O(N^2)，提交后发现超时，排除暴力法

思路1：动态规划

既然暴力法超时，那我们就想办法降低算法的时间复杂度，最常用的就是动态规划来降低时间复杂度。由于题目要求只能买卖一次，因此对于每天来说有两种状态 持有股票 没有持有股票

dp[i][0] //表示第 i+1天没有持有股票  (i是从0开始)
dp[i][1] //表示第 i+1天持有股票  

推导状态转移方程：

• 对于dp[i][0] 可能有两种情况：

1. dp[i-1][0] 前一天没有持有股票，当天也不购买股票
2. dp[i-1][1] +prices[i] 前一天持有股票，当天卖出

   dp[i][0] 就是 两种情况的最大值

• 对于dp[i][1] 有两种情况：

  1. 由于只能买卖一次，所以当天购买股票就是 -prices[i]

     1. 前一天持有股票，当天不进行任何操作 dp[i-1][1]

dp[i][1] 就是 两种情况的最大值

 //动态转移方程
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i]);
            
 dp[i][1] = Math.max(-prices[i],dp[i-1][1]);

结果是最后一天不持有股票的值 dp[n-1][0]

思路2：贪心（一次遍历）

因为我们在卖出股票之前必须先买入，所以我们可以使用一个变量 min 记录下之前所有天股票的最低价格，使用另一个变量max记录到当前为止最大收益，然后每遍历到一天就计算 这一天如果卖出股票所获得收益 并与max比较更新max

   //每次使用当天的价格减去之前天数的最小价格 更新max
max = Math.max(max,prices[i] - min);
            
 min = Math.min(min,prices[i]);

🏳️‍🌈3.代码实现

动态规划 代码实现：

import java.util.*;


public class Solution {
    /**
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
    public int maxProfit (int[] prices) {
         
        int n = prices.length;
        
        //下标i是从0开始
        //dp[i][0] 表示第i+1天不持有股票 从第一天到第i+1天的收益
        //dp[i][1] 表示第i+1天持有股票 从第一天到第i+1天的收益
      int[][] dp = new int[n][2];
        //初始化第一天不持有股票的收益0
        dp[0][0] = 0;
        //初始化第一天持有股票的收益 就是第一天买了当天的股票 -prices[0]
        dp[0][1] = -prices[0];
       
        //从第二天开始
        for(int i = 1;i < n; i++){
            
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i]);
            
            dp[i][1] = Math.max(-prices[i],dp[i-1][1]);
        }
        
        //最后一天不持有股票此时的值就是最大收益
        return dp[n-1][0];
    }
}

贪心 代码实现：

import java.util.*;
public class Solution {
    /**
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        
        //记录最小值 初始值为数据范围最大+1
        int min = 10001;
        //记录最大值，初始值为0
        int max = 0;
        
        int n = prices.length;
        
            //遍历数组记录所遍历过的价格的最小值  
        for(int i = 0;i < n; i++){
            
            //每次使用当天的价格减去之前天数的最小价格 更新max
            max = Math.max(max,prices[i] - min);
            
            min = Math.min(min,prices[i]);
         
        }   
        return max;
        
    }
}