121. Best Time to Buy and Sell Stock

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

Best Time to Buy and Sell Stock - LeetCode

난이도 : easy

 

문제

한 번의 거래로 낼 수 있는 최대 이익을 산출하라.

해당문제의 제약사항은 총길이가 10^5 임으로 브루트 포스로 풀 수 없다. time-limited 가 발생한다.

• 1 <= prices.length <= 10^5 

 

해당 문제는 아래처럼 도표를 그리면 어느 시점에 파는 것이 가장 큰 이득을 보는지 알 수 있다. 2일짜에 1원에 주식을 사고 5일짜에 6원에 팔면 가장 큰 수익을 얻게 된다.

코드

stack 을 이용한 풀이

stack의 top 은 현재 값과 비교하여 작은 값을 top 으로 유지한다. 만약 현재 값이 stack 에 탑보다 크다면 차이를 구하고 최대 크기를 갱신한다.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        
        // stack 을 이용해서 문제를 품
        // stack top 은 항상 작은 값을 넣고 현재 값가 비교하여 
        // 작으면 stack 을 비우고 현재 값을 top 으로 만든다.
        // 만약 현재 값이 stack 에 탑보다 크다면 크차이를 최대 크기로 출력한다.
        
        stack<int> st;
        st.push(987654321);
        
        int sol = 0;
        for(auto a:prices) {
            if (a < st.top()) {
                st.pop();
                st.push(a);
            }
            else {
                // 최대값을 계속 갱신
                sol = max(sol, a - st.top());
            }
        }
        
        return sol;
    }
};

스택을 사용해서 그런지? 최상위 하나만 갱신 하도록 했는데 생각보다 메모리를 많이 사용했다. 

저점과 현재 값과의 차이로 계산

지역변수를 선언해도 마찬가지도 공간복잡도가 큰차이가 없었다.

    int maxProfit(vector<int>& prices) {
        
        int profit = 0;
        int min_price = 987654321;
        for(int i = 0; i < prices.size(); i++) {
            min_price = min(prices[i], min_price);
            profit = max(profit, prices[i] - min_price);
        }
        
        return profit;
    }