if anybody is looking for a Java code...here it is int n = heights.length; int[] res = new int[n]; Stack st = new Stack(); st.push(heights[n-1]); res[n-1]=0; for(int i=n-2;i>=0;i--){ int visible = 0; while(st.size()>0 && heights[i]>st.peek()){ visible++; st.pop(); res[i] = visible; } if(st.size()>0){ visible++; res[i] = visible; } st.push(heights[i]); } return res;
// stores number of visible people per person in heights array int[] answer = new int[heights.length]; // last person cannot see anyone to the right answer[heights.length - 1] = 0; // keep track of heights of people visible to the right from current person Stack heightStack = new Stack(); // push last person's height onto stack, since iterating from right to left heightStack.push(heights[heights.length - 1]); // loop from right to left starting at second to last person for (int i = heights.length - 2; i >= 0; i--) { // reset visible count to zero int visiblePeople = 0; // while people still in stack and current person is taller than next while (heightStack.size() > 0 && heights[i] > heightStack.peek()) { // current person can see next person visiblePeople++; // remove shorter person from stack, since they will be blocked by current person heightStack.pop(); } // if stack not empty after loop ends (all shorter people have been removed), // there is at least one taller or equal-height person in stack who can be seen by current person if (heightStack.size() > 0) { // account for this person being visible visiblePeople++; } // store total number of people found visible for current person answer[i] = visiblePeople; // push current person's height onto stack for next comparison heightStack.push(heights[i]); } return answer;
Thank you! Very simple explanation
Thanks for the most simple explanation. Could you please make a separate video on the monotonic stack algorithm .. ?
Thank you!
could u plz make video on sum of subarray ranges ? It's also a question of monotonic stack..
Sure let me add it to my work queue. Make sure to subscribe so you don’t miss the video when it comes out
ruclips.net/channel/UCeOjJmGArxh1pOpa3DBTWuA this is the you tube channel they explained very well
Thank you very much
if anybody is looking for a Java code...here it is
int n = heights.length;
int[] res = new int[n];
Stack st = new Stack();
st.push(heights[n-1]);
res[n-1]=0;
for(int i=n-2;i>=0;i--){
int visible = 0;
while(st.size()>0 && heights[i]>st.peek()){
visible++;
st.pop();
res[i] = visible;
}
if(st.size()>0){
visible++;
res[i] = visible;
}
st.push(heights[i]);
}
return res;
// stores number of visible people per person in heights array
int[] answer = new int[heights.length];
// last person cannot see anyone to the right
answer[heights.length - 1] = 0;
// keep track of heights of people visible to the right from current person
Stack heightStack = new Stack();
// push last person's height onto stack, since iterating from right to left
heightStack.push(heights[heights.length - 1]);
// loop from right to left starting at second to last person
for (int i = heights.length - 2; i >= 0; i--) {
// reset visible count to zero
int visiblePeople = 0;
// while people still in stack and current person is taller than next
while (heightStack.size() > 0 && heights[i] > heightStack.peek()) {
// current person can see next person
visiblePeople++;
// remove shorter person from stack, since they will be blocked by current person
heightStack.pop();
}
// if stack not empty after loop ends (all shorter people have been removed),
// there is at least one taller or equal-height person in stack who can be seen by current person
if (heightStack.size() > 0) {
// account for this person being visible
visiblePeople++;
}
// store total number of people found visible for current person
answer[i] = visiblePeople;
// push current person's height onto stack for next comparison
heightStack.push(heights[i]);
}
return answer;
"obviously we go from right to left" why?
Because we want the next one, so we come from next to present, that is right to left