Intuition

Could you use the answer of previous spans?

Approach

Save the price and its span in the array.

Whenever the last value is less than the current day value, jump to the day of the last day span.

Complexity

• Time complexity: O(n)

• Space complexity: O(n)

Code

class StockSpanner {
    ArrayList<Pair<Integer,Integer>> list;
    public StockSpanner() {
        list = new ArrayList<>();
    }
    public int next(int price) {
        int index = list.size() - 1;
        int ans = 1;
        while(index!=-1){
            if(list.get(index).getKey()>price) break;
            int span = list.get(index).getValue();
            ans+=span;
            index-=span;
        }
        list.add(new Pair(price,ans));
        return ans;
    }
}
/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner obj = new StockSpanner();
 * int param_1 = obj.next(price);
 */
class StockSpanner {
    ArrayList<Pair<Integer,Integer>> list;

    public StockSpanner() {
        list = new ArrayList<>();
    }

    public int next(int price) {
        int index = list.size() - 1;
        int ans = 1;
        while(index!=-1){
            if(list.get(index).getKey()>price) break;
            int span = list.get(index).getValue();
            ans+=span;
            index-=span;
        }
        list.add(new Pair(price,ans));
        return ans;
    }
}


/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner obj = new StockSpanner();
 * int param_1 = obj.next(price);
 */
class StockSpanner {
    ArrayList<Pair<Integer,Integer>> list;

    public StockSpanner() {
        list = new ArrayList<>();
    }

    public int next(int price) {
        int index = list.size() - 1;
        int ans = 1;
        while(index!=-1){
            if(list.get(index).getKey()>price) break;
            int span = list.get(index).getValue();
            ans+=span;
            index-=span;
        }
        list.add(new Pair(price,ans));
        return ans;
    }
}


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

Enter fullscreen mode Exit fullscreen mode

GitHub repo for more solutions: Git
Leetcode profile: Leetcode: devn007

原文链接：Leetcode 901. Online Stock Span