Best Time to Buy and Sell Stock

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/submissions/1/

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Thoughts

观察到maxProfit是位置在后的最大值减去位置在前的最小值。那存下当前结点之前的最小值，再用当前结点减去它看是否是max profit即可。

Code

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n == 0) {
            return 0;
        }

        int min = prices[0];
        int max = 0;
        for (int i = 1; i < n; i++) {
            max = Math.max(max, prices[i] - min);
            min = Math.min(min, prices[i]);
        }

        return max;
    }
}

Analysis

时间复杂度O(n)