Leetcode 901. Online Stock Span
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 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); */ GitHub repo for more solutions: Git Leetcode profile: Leetcode: devn007
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> 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);
*/
GitHub repo for more solutions: Git
Leetcode profile: Leetcode: devn007
