Skip to content

Instantly share code, notes, and snippets.

@nikhilbchilwant
Created February 14, 2016 03:50
Show Gist options
  • Save nikhilbchilwant/32ec4fae0478602f06f5 to your computer and use it in GitHub Desktop.
Save nikhilbchilwant/32ec4fae0478602f06f5 to your computer and use it in GitHub Desktop.
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;
public class Solution {
public static Scanner sc = new Scanner(System.in);
public static Stack<Solution.Node> stack = null;
public static int ans = -1;
public static void main(String[] args){
stack = new Stack<Solution.Node>();
String line1 = sc.nextLine();
int N = Integer.parseInt(line1);
Solution.Node[] input = new Solution.Node[N];
String line2 = sc.nextLine();
String[] splittedInput=line2.split(" ");
int index=0;
for(String s : splittedInput){
int poisonAmnt = Integer.parseInt(s);
input[index] = new Solution().new Node(poisonAmnt, -1);
index++;
}
int elementIndex = 0;
while(elementIndex<N){
Node currentNode = input[elementIndex];
if(stack.isEmpty()){
currentNode.setDay(0);
ans= max(ans, 0);
stack.push(currentNode);
}
else if(currentNode.getPoisonAmt()>stack.peek().getPoisonAmt()){
currentNode.setDay(1);
ans= max(ans, 1);
stack.push(currentNode);
}
else if(currentNode.getPoisonAmt()<stack.peek().getPoisonAmt()){
int maxDay = 0;
while(!stack.isEmpty() && (stack.peek().getPoisonAmt()>currentNode.getPoisonAmt())){
Node topElement = stack.pop();
maxDay=max(maxDay, topElement.getDay());
}
if(stack.isEmpty()){
currentNode.setDay(0);
ans= max(ans, 0);
stack.push(currentNode);
}
else{
currentNode.setDay(maxDay+1);
ans= max(ans, maxDay+1);
stack.push(currentNode);
}
}
elementIndex++;
}
System.out.println(ans);
}
private static int max(int maxDay, int day) {
if(maxDay>day){
return maxDay;
}
else{
return day;
}
}
private class Node{
private int poisonAmt;
private int day=-1;
public Node(int poisonAmt, int day){
this.poisonAmt=poisonAmt;
this.day=day;
}
public void setDay(int i) {
this.day=i;
}
public int getDay(){
return this.day;
}
public int getPoisonAmt(){
return this.poisonAmt;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment