[Monotonic Stack][Medium] 901. Online Stock Span

 

https://leetcode.com/problems/online-stock-span/description

LeetCode - The World's Leading Online Programming Learning Platform

 

Q. next()를 통해 그 날의 stock price가 주어진다. 

  연속해서 이 값보다 같거나 적은 날의 수를 반환하라.

 

Solution. 

  주어진 모든 input를 list나 vector로 저장한다. 

  뒤에서 부터 주어진 값보다 같거나 작은 순간까지 for loop을 돌린다. 

  간단 명료 하다. 

  하지만, 이 방법은 매 next 마다 O(N)의 검색을 해야 한다. 

  결과를 보니 역시나다. 

 

더 빠른 방법은 검색 대상을 줄이는 것이다. 

하지만 어떻게?

자기보다 연속된 작은 수를 없애고, 현재값에 그 없앤 수 정보를 같이 기록한다.

그러면, list에서 뒤에서 연속된 어떤 수보다 작은 값이 그 수에 같이 정보가 들어 있으므로, loop가 필요 없게 된다. 

 

이런 방식으로 논리를 전개해 코드를 만들어 본다.

 

stack<pair<int, int>> sPrices;
int next(int price)
{
    int cnt = 1;
    while (!sPrices.empty())
    {
        if (price >= sPrices.top().first)
        {
            cnt += sPrices.top().second;
            sPrices.pop();
        }
        else
            break;
    }
    sPrices.push(make_pair(price, cnt));

    return cnt;
}

 

 

훨씬 나은 결과를 얻었다.