刷题-买卖股票的最佳时机-C++/java(暴力法，动态规划，单调栈等）

一、问题描述

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

二、思路分析

1.动态规划思想
记录【今天之前买入的最小值】
计算【今天之前最小值买入，今天卖出的获利】，也即【今天卖出的最大获利】
比较【每天的最大获利】，取最大值即可。
2.暴力法
如果想要获取最大的利润，那么我们就需要在最小的时候买入，在之后最大的某一天卖出。
也就是求两个数字之间的差值，但是必须是后边减去前边。
形式上，对于每组i 和 j（其中 j>i）我们需要找出max(prices[j]−prices[i])
3.一次遍历法则
股票问题的方法就是 动态规划，因为它包含了重叠子问题，即买卖股票的最佳时机是由之前买或不买的状态决定的，而之前买或不买又由更早的状态决定的…
由于本题只有一笔交易（买入卖出），因此除了动态规划，我们还可以使用更加简便的方法实现。
在题目中，我们只要用一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。
因此，我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。
4.单调栈
一眼看过去，这个题本质就是要求某个数与其右边最大的数的差值，这符合了单调栈的应用场景 当你需要高效率查询某个位置左右两侧比他大（或小）的数的位置的时候。
Largest Rectangle in Histogram
https://leetcode.cn/problems/largest-rectangle-in-histogram/
Maximal Rectangle
https://leetcode.cn/problems/maximal-rectangle/

单调栈的作用是:用 O(n) 的时间得知所有位置两边第一个比他大(或小)的数的位置。

5.贪心法则

三、知识点

1.动态规划
动态规划有几个典型特征，最优子结构、状态转移方程、边界、重叠子问题。
什么样的问题可以考虑使用动态规划解决呢？——如果一个问题，可以把所有可能的答案穷举出来，并且穷举出来后，发现存在重叠子问题，就可以考虑使用动态规划。比如一些求最值的场景，如最长递增子序列、最小编辑距离、背包问题、凑零钱问题等等，都是动态规划的经典应用场景。
动态规划的解题思路——动态规划的核心思想就是拆分子问题，记住过往，减少重复计算。
上面已经知道动态规划算法的核心是记住已经求过的解，记住求解的方式有两种：①自顶向下的备忘录法 ②自底向上。
动态规划的核心思想是把原问题分解成子问题进行求解，也就是分治的思想。（大事化小，小事化了）

2.暴力法
很多ACM题目都不能直接用暴力法解决，基本上是超时的，所以做题目时暴力法是万不得已才用的。
暴力法，也叫穷举法。 它要求设计者找出所有可能的方法，然后选择其中的一种方法，若该方法不可行则试探下一种可能的方法。 该方法逻辑清晰、简单，编写程序简洁。 在某些情况下，算法规模不大时，使用优化的算法没有必要，而且某些优化算法本身较为复杂，在规模不大时可能因为复杂的算法浪费时间，反而不如简单的蛮力搜索。 使用暴力法的几种情况： 搜索所有的解空间和路径；2. 直接进行计算；3. 在问题规模不是很大的情况下，现实问题的模拟与仿真。 使用暴力方法将所有的可能解列出来，看这些解是否满足要求或者条件，从中选择出符合要求的解。 这个题目可以用暴力法解决，只需要测试满足的解即可。 值得注意的是需要考虑取值范围和多解时候的情况。
深度优先遍历和广度优先遍历是最常见的。
3.单调栈
所谓 单调栈 则是在栈的 先进后出 基础之上额外添加一个特性：从栈顶到栈底的元素是严格递增（or递减）。
具体进栈过程如下：
对于单调递增栈，若当前进栈元素为 e，从栈顶开始遍历元素，把小于 e 或者等于 e 的元素弹出栈，直接遇到一个大于 e 的元素或者栈为空为止，然后再把 e 压入栈中。
对于单调递减栈，则每次弹出的是大于 e 或者等于 e 的元素。
要知道单调栈的适用于解决什么样的问题，我们首先需要知道单调栈的作用。单调栈分为单调递增栈和单调递减栈，通过使用单调栈我们可以访问到下一个比他大（小）的元素（或者说可以）。也就是说在队列或数组中，我们需要通过比较前后元素的大小关系来解决问题时我们通常使用单调栈。下面我们通过简单介绍单调减栈和单调增栈问题来进一步说明使用单调栈处理问题的过程。
4.贪心法
贪心算法一般按如下步骤进行： ①建立数学模型来描述问题 。 ②把求解的问题分成若干个子问题 。 ③对每个子问题求解，得到子问题的局部最优解 。 ④把子问题的解局部最优解合成原来解问题的一个解 。
贪心算法，又名贪婪法，是寻找最优解问题的常用方法，这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好/最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好/最优的解。

5.JAVA和C++运算时间快慢和决定
java这些年来在性能上提升了非常多，甚至平均性能已经与C++不相伯仲了，但是在某些对性能要求极高的情况下还是不及C++。也就是说C++的性能天花板要比Java高一些。但反过来，Java的开发效率和其生态也是C++没法比

四、代码解决

1动态规划java实现

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length <= 1)
            return 0;
        int min = prices[0], max = 0;
        for(int i = 1; i < prices.length; i++) {
            max = Math.max(max, prices[i] - min);
            min = Math.min(min, prices[i]);
        }
        return max;
    }
}

动态规划C++

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0; // 边界条件
        int minprice = prices[0];
        vector<int> dp (n, 0);

        for (int i = 1; i < n; i++){
            minprice = min(minprice, prices[i]);
            dp[i] = max(dp[i - 1], prices[i] - minprice);
        }
        return dp[n - 1];
    }
};

2暴力法C++
（下面这个解决方案是超出时间限制了）

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = (int)prices.size(), ans = 0;
        for (int i = 0; i < n; ++i){
            for (int j = i + 1; j < n; ++j) {
                ans = max(ans, prices[j] - prices[i]);
            }
        }
        return ans;
    }
};

3.一次遍历法C++

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int inf = 1e9;
        int minprice = inf, maxprofit = 0;
        for (int price: prices) {
            maxprofit = max(maxprofit, price - minprice);
            minprice = min(price, minprice);
        }
        return maxprofit;
    }
};

4.单调栈的C++

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        vector<int> St;
        prices.emplace_back(-1); // 哨兵👨‍✈️
        for (int i = 0; i < prices.size(); ++ i){
            while (!St.empty() && St.back() > prices[i]){ //维护单调栈📈
                ans = std::max(ans, St.back() - St.front()); //维护最大值
                St.pop_back();
            }
            St.emplace_back(prices[i]);
        }

        return ans;
    }
};

5.贪心法则实现java
（这个速度是超过百分之百的用户的，使用的是贪心法则）

class Solution {
    public int maxProfit(int[] prices) {
        //贪心思想
        int max=0;
        int cur=prices[0];
        for(int p : prices){
            //如果比cur小则替换
            if(p<cur){
                cur=p;
                continue;
            }
            //如果比 cur 大则计算卖出最大获利
            if(p>cur){
                max=Math.max(max,p-cur);
            }

        }
        return max;
    }
}

五、总结对比

1.方案1动态规划法
时间复杂度：\mathcal{O}(n)O(n)。
空间复杂度：\mathcal{O}(n)O(n)。

2.方案2暴力法的复杂度
时间复杂度：O(n^2)
空间复杂度：O(1)。只使用了常数个变量。

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