May LeetCoding Challenge[Day19] - Online Stock Span

Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock's price for the current day.

The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today's price.

For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].

Input: ["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]] Output: [null,1,1,1,2,1,4,6]

Explanation:
First, S = StockSpanner() is initialized. Then: S.next(100) is called and returns 1,
S.next(80) is called and returns 1,
S.next(60) is called and returns 1,
S.next(70) is called and returns 2,
S.next(60) is called and returns 1,
S.next(75) is called and returns 4,
S.next(85) is called and returns 6.

Note that (for example)

S.next(75) returned 4, because the last 4 prices (including today's price of 75) were less than or equal to today's price.

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 해당 문제가 명확하게 이해가 가지 않았고, 유튜브 학습 후, 알고리즘 풀었습니다.

 

https://www.youtube.com/watch?v=JsYyLiGXHsc&t=173s

 

2. 알고리즘 작성 중, 어려운 점 & 깨달은 점

 

- Stack에 여러 개의 변수를 저장해야하는 로직이 필요했는데, 그 때는 2차원 배열을 사용하면 쉽게 구현할 수 있다.

 

3. 내가 작성한 알고리즘

 

class StockSpanner {
    int top;
    int[][] stack;
    public StockSpanner() {
        stack = new int[2][1000];
        top = -1;
    }
    
    public int next(int price) {
        int span = 1;
        while(top >= 0 && stack[0][top] <= price){
            span += stack[1][top];
            top--;
        }
        top++;
        stack[0][top] = price;
        stack[1][top] = span;
        
        return span;
    }
        
}

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner obj = new StockSpanner();
 * int param_1 = obj.next(price);
 */

 

4. 결과

 

5. 깨닫고 있는 점

 - 문제를 명확하게 파악하고, 손으로 필기하면 알고리즘이 명확하게 이해할 수 있다.

 

문제 : https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/536/week-3-may-15th-may-21st/3334/

Account Login - LeetCode