121. 买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。 示例 2:

输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解 :

思路一 : 暴力法

  • 两层循环，遍历每一种可能性
  • 时间复杂度 : O(n ^ 2)
  • 空间复杂度 : O(1)
  • 导致提交后，超时
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

    /**
     
     暴力法
     遍历每一种可能
     时间复杂度 : O(n ^ 2)
     空间复杂度 : O(1)
     
     */
    int maxProfit(vector<int>& prices) {
        if (prices.size() <= 1) return 0;
        int max = 0;
        for (int i = 0; i < prices.size() - 1; i ++) {
            for (int j = i + 1; j < prices.size(); j ++) {
                
                int diff = prices[j] - prices[i];
                max = max > diff ? max : diff;
            }
        }
        return max;
    }
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

    /**

     暴力法
     遍历每一种可能
     时间复杂度 : O(n ^ 2)
     空间复杂度 : O(1)

     */
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        if (prices.length == 1) return 0;

        int max = 0;
        for (int i = 1; i < prices.length; i++) {

            for (int j = 0; j < i; j++) {
                if (prices[i] <= prices[j]) continue;
                max = Math.max(max,prices[i] - prices[j]);
            }
        }

        return max;
    }

思路二 : 动态规划

  • 记录最小价值 minprice 为数组首元素
  • 记录最大利润 maxprofit
  • 从数组 idx = 1开始遍历
  • 当 minprice < prices[i] 时, 说明当前下标没有利润。将 min 赋值为 prices[i]
  • 当 minprice > prices[i] 时, 当前下标的利润为 prices[i] - min.
    • maxprofit = max(maxprofit, prices[i] - min)
  • 时间复杂度 : O(n)
  • 空间复杂度 : O(1)
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

    /**
     
     动态规划
     记录最小价值 min 为数组首元素
     记录最大获利润 res
     
     从 index为1 元素开始遍历
     当最小值 > prices[i] 时, 说明当前下标没有利润。 将 min = prices[i] 即可
     当最小值 < prices[i] 时, res = max(res,prices[i] - min);
     
     时间复杂度 : O(n)
     空间复杂度 : O(1)
     
     */
    int maxProfit1(vector<int>& prices) {
        if (prices.size() <= 1) return 0;
        
        int res = 0, min = prices[0];
        
        for (int i = 1; i < prices.size(); i ++) {
            if (min > prices[i]) {
                min = prices[i];
                continue;
            }
            res = max(res,prices[i] - min);
        }
        return res;
    }
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/**
     动态规划
     记录最小价值 min 为数组首元素
     记录最大获利润 res

     从 index为1 元素开始遍历
     当最小值 > prices[i] 时, 说明当前下标没有利润。 将 minprice = prices[i] 即可
     当最小值 < prices[i] 时, maxprofit = max(maxprofit,prices[i] - minprice);

     时间复杂度 : O(n)
     空间复杂度 : O(1)

     */
    public int maxProfit1(int[] prices) {
        if (prices.length <= 1) return 0;
        int maxprofit = 0;
        int minprice = prices[0];

        for (int i = 1; i < prices.length; i++) {

            if (minprice > prices[i]){
                minprice = prices[i];
                continue;
            }
            maxprofit = Math.max(maxprofit, prices[i] - minprice);
        }
        return maxprofit;
    }

思路三 : 单调栈

  • 个人感觉趁着机会复习下单调栈的操作可以的
  • 但是解决此题目没有太大必要，我们只要维护一个 minprice 就可以了 。 没必要使用 单调递增栈 来存储最小值
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

/**
     *
     * next greater number问题
     * 使用单调栈
     *
     * 可以解决问题，顺便复习一下单调栈的用法也不错
     * 但是个人感觉，用的比较牵强。
     * 本可以使用一个 minprice 解决的问题
     * 何必使用一个栈来解决呢？ 并且栈上，貌似最多存放的元素也是 1 个
     * 相当于 用 stack 来存放 minprice
     *
     * */

    public int maxProfit2(int[] prices){
        if (prices == null || prices.length <= 1) return 0;

        Stack<Integer> stack = new Stack<>();
        stack.push(prices[0]);

        int maxprofit = 0;
        for (int i = 1; i < prices.length; i++) {
            int price = prices[i];

            while (!stack.isEmpty() && price < stack.peek()){
                stack.pop();
            }

            if (stack.isEmpty()) stack.push(price);

            maxprofit = Math.max(maxprofit, price - stack.peek());
        }

        return maxprofit;
    }

122. 买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。 示例 2:

输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。 示例 3:

输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1 <= prices.length <= 3 * 10 ^ 4 0 <= prices[i] <= 10 ^ 4

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解 :

  • 此题目使用贪心算法
  • 走每一步时，如果递增，就把递增的数量，加入结果中
  • 最终走完后，我们就得到了最终结果
  • 在leetcode题解区截了张图， 帮助理解
  • 一句话就是 : 加上所有上升线段的值

![image-20200710132159889](/Users/liuxiaoyong/Library/Application Support/typora-user-images/image-20200710132159889.png)

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

    int maxProfit(vector<int>& prices) {
        if (prices.size() <= 1) return 0;
        
        int res = 0;
        for (int i = 1; i < prices.size(); i ++) {
            res += max(0,prices[i] - prices[i - 1]);
        }
        
        return res;
    }
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

    static int maxProfit(int[] prices) {

        if(prices == null || prices.length <= 1) return 0;
        int res = 0;

        for (int i = 1; i < prices.length; i++) {
            int diff = prices[i] - prices[i-1];
            if (diff > 0){
                res += diff;
            }
        }

        return res;
    }