算法：数组中的最大差值---“打擂台法“

分手后的思念是犯贱 2024-03-06 05:41 93阅读 0赞

#### 1、题目： ####

给定一个整数数组 nums，找出给定数组中两个数字之间的最大差值。要求，第二个数字必须大于第一个数字。

#### 2、分析特点： ####

*  **`求最大差值 ==> 最大值 - 最小值`**
 *  只需要遍历价格数组一遍，记录历史最小值，非最小值的考虑是最大值。

#### 3、代码： ####

public int maxProfit(int nums[]) {
        
            int minNum = Integer.MAX_VALUE;
            int maxNum = 0;
            for (int i = 0; i < nums.length; i++) {
        
                if (nums[i] < minNum) {
        
                    minNum = nums[i];
                } else if (nums[i] - minNum > maxNum) {
        
                    maxNum = nums[i] - minNum;
                }
            }
            return maxNum;
        }

#### 4、复杂度分析： ####

>  *  时间复杂度：O(n)，只需要遍历一次。
>  *  空间复杂度：O(1)，只使用了常数个变量。

#### 5、总结： ####

使用打擂台的思想，遍历的时候，考虑当前值是最小值，则记录最小值，否则考虑当前值是最大值，进行更新。

#### 6、其他解法–暴力法 ####

![2896a78701897cf30a472bbe844580c4.png][]

public int maxProfit(int[] nums) {
        
            int maxNum = 0;
            for (int i = 0; i < nums.length - 1; i++) {
        
                for (int j = i + 1; j < nums.length; j++) {
        
                    int subValue = nums[j] - nums[i];
                    if (subValue > maxNum) {
        
                        maxNum = subValue;
                    }
                }
            }
            return maxNum;
        }

##### 6-1、复杂度分析 #####

![22ad5ad4ec3db330cf029006a33ec0bc.png][]

#### 7、题目变化 ####

给定一个数组 prices ，它的第 i 个元素 prices\[i\] 表示一支给定股票第 i 天的价格。

你只能选择 **某一天** 买入这只股票，并选择在 **未来的某一个不同的日子** 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

![239736f09a0034a05c1c4382d732f0f3.png][]

> 我们来假设自己来购买股票。随着时间的推移，每天我们都可以选择出售股票与否。那么，假设在第 i 天，如果我们要在今天卖股票，那么我们能赚多少钱呢？
> 
> 显然，如果我们真的在买卖股票，我们肯定会想：如果我是在历史最低点买的股票就好了！太好了，在题目中，我们只要用一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices\[i\] - minprice。
> 
> 因此，我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。

##### 7-1、一次遍历 #####

public int maxProfit(int prices[]) {
        
            int minprice = Integer.MAX_VALUE;
            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;
        }

###### ■ 复杂度分析： ######

>  *  时间复杂度：O(n)，只需要遍历一次。
>  *  空间复杂度：O(1)，只使用了常数个变量。

##### 7-2、暴力法 #####

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;
        }
    }

###### ■ 复杂度分析： ######

![c2dc1c8019bb567115a8f87866c91c22.png][]

**如果本文对你有帮助的话记得给一乐点个赞哦，感谢！**

[2896a78701897cf30a472bbe844580c4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/06/9c6281d3e06345a09804ba5cf51b2114.png
[22ad5ad4ec3db330cf029006a33ec0bc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/06/4a3b46246bbb4873bfdef4ebe6d4a46b.png
[239736f09a0034a05c1c4382d732f0f3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/06/de210f3efe894c84a3016f6834852ffc.png
[c2dc1c8019bb567115a8f87866c91c22.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/06/1e8c8bf712cf4c26ae9d416cfbdd4204.png