121. Best Time to Buy and Sell Stock

2018/03/17 15:52
阅读数 0

原题链接:https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/ 解答如下:

/**
 * Created by clearbug on 2018/2/26.
 *
 * 这道题目是《剑指 Offer》书上的原题,面试题 63:股票的最大利润
 *
 * 刚开始在 LeetCode 上面看到这道级别为 easy 的题目时,我是无可奈何花落去的!看了《剑指 Offer》上面的解析后才明白真的很简单!
 */
public class Solution {

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.maxProfit1(new int[]{1, 22}));
        System.out.println(s.maxProfit1(new int[]{7, 1, 5, 3, 6, 4}));
        System.out.println(s.maxProfit1(new int[]{7, 6, 4, 3, 1}));

        System.out.println(s.maxProfit2(new int[]{1, 22}));
        System.out.println(s.maxProfit2(new int[]{7, 1, 5, 3, 6, 4}));
        System.out.println(s.maxProfit2(new int[]{7, 6, 4, 3, 1}));
    }

    /**
     * 方法一:Brute-Force,Submission Result:Time Limit Exceeded
     *
     * 时间复杂度:O(n^2)
     *
     * @param prices
     * @return
     */
    public int maxProfit1(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }

        int res = 0;
        for (int i = 0; i < prices.length - 1; i++) { // 在 i 买入
            for (int j = i + 1; j < prices.length; j++) { // 在 j 卖出
                if (prices[j] - prices[i] > res) {
                    res = prices[j] - prices[i];
                }
            }
        }
        return res;
    }

    /**
     * 方法二:优雅简洁。
     * 思路就是记录当前位置前面所有元素的最小值即可,多么简单啊,可惜刚开始我就是没想到!
     *
     * 时间复杂度:O(n)
     *
     * @param prices
     * @return
     */
    public int maxProfit2(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }

        int res = 0;

        int min = prices[0];
        for (int i = 1; i < prices.length; i++) { // 以 min 买入,在 i 卖出
            if (prices[i] - min > res) {
                res = prices[i] - min;
            }

            if (prices[i] < min) {
                min = prices[i];
            }
        }
        return res;
    }

}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部