121.Best_Time_to_Buy_and_Sell_Stock.md

121. Best Time to Buy and Sell Stock

• Amazon, Facebook, Bloomberg, Microsoft, Apple, Google, ...
• Array, Dynamic Programming
• Similar Questions:
  • 53. Maximum Subarray
  • 121. Best Time to Buy and Sell Stock
  • 122. Best Time to Buy and Sell Stock II
  • 123.Best Time to Buy and Sell Stock III
  • 188. Best Time to Buy and Sell Stock IV
  • 309. Best Time to Buy and Sell Stock with Cooldown

Method 1. One Pass

Key Points:

1. Use a variable to track and store the minimum price.
2. 从头到尾遍历整个 array，如果 curr price 小于 previous min price，则说明不能卖掉，因为 previous min price 是买入价格，如果比买入价格 小的话，则说明亏损。所以当遇到比 previous min price 小的 price 就更新 min price。
3. 当遇到比 min price 大的价格，就可以选择卖出，更新可获得的最大利润。

class Solution {
    public int maxProfit(int[] prices) {
        if(prices==null || prices.length<2) {
            return 0;
        }
        
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = Integer.MIN_VALUE;
        for(int price: prices) {
            if(price < minPrice) {
                minPrice = price;
            } else {
                maxProfit = Math.max(maxProfit, price - minPrice);
            }
        }
        return (maxProfit == Integer.MIN_VALUE) ? 0 : maxProfit;
    }
}

Complexity Analysis

1. Time complexity : O(n). Only a single pass is needed.
2. Space complexity : O(1). Only two variables are used.