【LeetCode】 121. 买卖股票的最佳时机 2020年3月9日

叁歲伎倆 2021-06-10 20:37 319阅读 0赞

## <table>   <tbody>    <tr>     <td><font>题目</font></td>    </tr>   </tbody>  </table> ##

题目传送门：[传送门][Link 1]  
简单的说这道题目就是找最大差值，这个差值必须是后边的数字减去前边的数字  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

## <table>   <tbody>    <tr>     <td><font>题解</font></td>    </tr>   </tbody>  </table> ##

### 暴力算法： ###

public class Solution { 
        public int maxProfit(int prices[]) { 
            int maxprofit = 0;
            for (int i = 0; i < prices.length - 1; i++) { 
                for (int j = i + 1; j < prices.length; j++) { 
                    int profit = prices[j] - prices[i];
                    if (profit > maxprofit)
                        maxprofit = profit;
                }
            }
            return maxprofit;
        }
    }

### 优化算法： ###

不写了，直接贴了leetcode官方的题解，写的比我想得好

假设给定的数组为： \[7, 1, 5, 3, 6, 4\]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 1]  
使我们感兴趣的点是上图中的峰和谷。我们需要找到最小的谷之后的最大的峰  
我们可以维持两个变量——minprice 和 maxprofit，它们分别对应迄今为止所得到的最小的谷值和最大的利润（卖出价格与最低价格之间的最大差值）

class Solution { 
        public int maxProfit(int[] prices) { 
            if(prices.length == 0) return 0;
            int minprice = prices[0];
            int maxprofit = 0;
            for(int 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;
        }
    }

[Link 1]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/96deaa37094f4a8499a9fb119cbd6746.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 1]: /images/20210529/7e929b18f1e84f3fafb73c7a36ae4e9d.png