We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
It can be solved by using stack.
Let's take a look at the example below:
1,10,9,2,8,7,6,5,4,3. After 2 days, it will become 1,2,6,5,4,3. After 4 more days, it will become 1 and no more dying. One thing we can notice for a plant at idx i, if the left one at i - k is smaller than i, it can eliminate all the plants the i can eliminate. Also, a plant can finally eliminate all the plants has more pesticide(greater value) on its right hand side. So if we know how many days a plant at idx i, we can know how many days the left plants need to eliminate the plants. Below is a concise Java solution, which better explains the idea:
staticclassPair{intval,count;publicPair(intval,intcount){this.val=val;this.count=count;}}// Complete the poisonousPlants function below.staticintpoisonousPlants(int[]p){Stack<Pair>stack=newStack<>();intcnt=0;for(inti=p.length-1;i>=0;i--){inttemp=0;while(!stack.empty()&&p[i]<stack.peek().val){temp++;Pairpair=stack.pop();temp=Math.max(temp,pair.count);}cnt=Math.max(cnt,temp);stack.push(newPair(p[i],temp));}returncnt;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Poisonous Plants
You are viewing a single comment's thread. Return to all comments →
It can be solved by using stack. Let's take a look at the example below: 1,10,9,2,8,7,6,5,4,3. After 2 days, it will become 1,2,6,5,4,3. After 4 more days, it will become 1 and no more dying. One thing we can notice for a plant at idx
i
, if the left one ati - k
is smaller thani
, it can eliminate all the plants thei
can eliminate. Also, a plant can finally eliminate all the plants has more pesticide(greater value) on its right hand side. So if we know how many days a plant at idxi
, we can know how many days the left plants need to eliminate the plants. Below is a concise Java solution, which better explains the idea: