(Array, Easy) Best Time to Buy and Sell Stock

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

단순하게 2중 for문으로 푸는 경우 시간초과 발생함. 다른 방법으로 풀어야 한다.

Constraints:
1 <= prices.length <= 10^5
0 <= prices[i] <= 10^4

class Solution {
    public int maxProfit(int[] prices) {
        
        int result = 0;

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

            for (int j=i+1; j<prices.length; j++) {
                int max = prices[j];
                if (min < max) result = Math.max(result, max - min);
            }
        }

        return result;
    }
}

다른 방법이 뭐가 있을까?
최대한 적게 순회하도록 min, max 인덱스를 주고 이동하는 방식으로 풀었을 때
3ms / 62.31 MB로 통과는 되었으나 7.30%만을 Beats한 것을 볼 수 있다.

class Solution {
    public int maxProfit(int[] prices) {
        
        int result = 0;
        int start = 0;
        int end = start + 1;

        while (end < prices.length) {

            if (prices[start] > prices[end]) {
                start++;
                continue;
            }

            if (prices[end] >= prices[start]) {
                result = Math.max(result, prices[end] - prices[start]);
                end++;
                continue;
            }
        }

        return result;
    }
}

참고
Solutions 참고 시 1ms 더 빠르게 풀 수 있는 방법이 있다.
위에 내가 풀었던 방법은 아무래도 start == end 케이스를 만나기 마련인데,
아래 방법대로 하면 무조건 O(n)이기 때문에 상대적으로 더 빠른 결과를 나타낸 것 같다.

아이디어는 비슷하다.
profit는 Math.max로 계속 갈아치워 주되 최소값(buyPrice)을 갱신하여 매번 갱신하면 된다.

class Solution {
    public int maxProfit(int[] prices) {
        
        int buyPrice = prices[0];
        int profit = 0;

        for (int i = 1; i < prices.length; i++) {
            if (buyPrice > prices[i]) {
                buyPrice = prices[i];
            }

            profit = Math.max(profit, prices[i] - buyPrice);
        }

        return profit;        
    }
}