Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package com.test.project.stockSpan;
- import java.util.Stack;
- /*Span of a stock on a given day, is the maximum number of consecutive days just before the given day, for which the price of the stock is less than or equal to the price of stock on the given day.
- Let Price(i) = price of the stock on day "i".
- Span(i) = max{k : k<=i and Price(j)<=Price(i) for j=i-k, .., i}
- Thus, if Price(i-1)>Price(i), then Span(i)=0.*/
- public class StockSpan {
- public static int[] spanOfStocks(int[] price, int n, boolean useStacks) {
- if(!(useStacks))
- {
- //Calculate span in O(n^2) time without using stacks
- int[] span1 = new int[n];
- for(int i=0;i<=n-1;i++)
- {
- int k=0;
- boolean done = false;
- while((!done)&&(k<=i))
- {
- if(price[i-k]<=price[i])
- { k++;}
- else
- { done = true;}
- }
- span1[i] = k;
- }
- return span1;
- }
- //Calculate span in O(n) time using stacks
- int[] span2 = new int[n];
- Stack<Integer> stack = new Stack<Integer>();
- for(int i=0;i<=n-1;i++)
- {
- int k=0;
- boolean done = false;
- while((!(stack.isEmpty())) && (!done))
- {
- if(price[i]>=price[stack.peek()])
- {stack.pop();}
- else
- {done = true;}
- }
- int h = 0;
- if(stack.isEmpty())
- {h=-1;}
- else
- {h=stack.peek();}
- span2[i]=h-i;
- stack.push(i);
- }
- return span2;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement