Advertisement
Guest User

Solution to the stock span problem

a guest
Oct 4th, 2012
337
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package com.test.project.stockSpan;
  2.  
  3. import java.util.Stack;
  4.  
  5. /*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.
  6. Let Price(i) = price of the stock on day "i".
  7. Span(i) = max{k : k<=i and Price(j)<=Price(i) for j=i-k, .., i}
  8. Thus, if Price(i-1)>Price(i), then Span(i)=0.*/
  9.  
  10. public class StockSpan {
  11.    
  12.     public static int[] spanOfStocks(int[] price, int n, boolean useStacks) {
  13.         if(!(useStacks))
  14.         {
  15.             //Calculate span in O(n^2) time without using stacks
  16.             int[] span1 = new int[n];
  17.             for(int i=0;i<=n-1;i++)
  18.             {
  19.                 int k=0;
  20.                 boolean done = false;
  21.                 while((!done)&&(k<=i))
  22.                 {
  23.                     if(price[i-k]<=price[i])
  24.                     {   k++;}
  25.                     else
  26.                     {   done = true;}
  27.                 }
  28.                 span1[i] = k;
  29.             }
  30.             return span1;
  31.         }
  32.         //Calculate span in O(n) time using stacks
  33.         int[] span2 = new int[n];
  34.         Stack<Integer> stack = new Stack<Integer>();
  35.         for(int i=0;i<=n-1;i++)
  36.         {
  37.             int k=0;
  38.             boolean done = false;
  39.             while((!(stack.isEmpty())) && (!done))
  40.             {
  41.                 if(price[i]>=price[stack.peek()])
  42.                 {stack.pop();}
  43.                 else
  44.                 {done = true;}
  45.             }
  46.             int h = 0;
  47.             if(stack.isEmpty())
  48.             {h=-1;}
  49.             else
  50.             {h=stack.peek();}
  51.             span2[i]=h-i;
  52.             stack.push(i);
  53.         }
  54.         return span2;
  55.     }
  56. }
Advertisement
RAW Paste Data Copied
Advertisement