901. Online Stock Span

• 이전에 비슷한 접근법을 요구하는 문제가 있었는데, 그 기억대로 접근해서 한번에 해결.
• 무식하게 매번 전체 array 를 search 할수도 있는데 그러면 Time limt exception 이 뜰거라고 생각했다. 그런데 그렇게 해서도 accept  가 된 솔루션이 있어보이긴 했지만 아무튼.
• 요지는 두  array 를 관리 하면서, 현재  price 와 span 을 기록하는데, 현재를 기준으로, 
• 현재보다 이전 날짜의 span 은 그 날보다 가격이 같거나 작은날이 며칠인지를 이야기해주고 있으므로, 하루씩 back 할 필요 없이, 이 span 만큼 건너뛰어서 체크를 할수 있다. 물론 index outOfBound 는 피해야 한다.
• 처음 submit 할때는, 계산하는 함수를 따로 만들어서 뺐었는데, 그랬더니 32ms 가 나왔다.
• 가장 빠른 성능은 17ms 여서 뭔가 하고 봤는데 내 접근이랑 똑같은데 함수 호출만 없는거였다.
• 그래서 나도 private 함수로 뺀 부분을 그냥 합쳤더니 17ms 가 나왔다. 
• 보통 이런 함수 호출이 성능에 그만큼 큰 영향을 주나 싶지만, 주어진 조건에 테스트케이스당 최대 만번의  호출을 하고, 전체 테스트케이스 합산시 15만번의 호출까지 한다고 하니. 함수스택 한번 들어갔다 나오는게 늘어나는만큼 유의미한 차이가 있긴 있었나보다. 그래봤자 15ms 가 일반적으로 쉽게 인식 가능한 범위는 아니지만.
• 아래의 calculateNewSpan 이 문제의 그 추가적인 함수 호출이었다.

class StockSpanner {

    private int[] priceArray;
    private int[] spanArray;
    private int count;

    public StockSpanner() {
        priceArray = new int[10000];
        spanArray =  new int[10000];
        count = 0;
    }

    public int next(int price) {
        priceArray[count]= price;
        if(count==0){
            spanArray[count]=1;
            count++;
            return spanArray[0];
        }else{
            int newSpan = calculateNewSpan();
            spanArray[count] =newSpan;
            count++;
            return newSpan;
        }
    }

    private int calculateNewSpan(){
        int newSpan = 1;
        int idx = count-1;
        while(idx>=0 && priceArray[idx]<=priceArray[count]){
            newSpan = newSpan+spanArray[idx];
            idx = idx-spanArray[idx];
        }
        return newSpan;
    }
}