https://leetcode.com/problems/number-of-visible-people-in-a-queue/ from Facebook

Thinking process:

If there’s one person on your right who is taller than you, then you’ll not be able to see any person after him/her. For example, if your height is 5, and there’s a person b on your right whose height is 8, then you’ll not able to see any person after b no matter they are taller than 8 or not.

In other words, if we go from left to right, whenever we meet a person who is taller then us, the number of the person we can see is fixed since we’re not able to see anymore person. This characteristic is a hint to use the monotonic stack.

To use the monotonic stack, we usually go from left to right. We are going to maintain a monotonic decreasing stack because if we find any person taller than the top of the stack, then we don’t need the top anymore because the answer of that top person is fixed.

The other thing to determine is the number of person we can see. Obviously when we see a person taller than us on our right, we should add one to the answer at our position. The other case is when we see another person who is shorter than us, but there’s no other person in between who is taller than him/her, we should add one as well.

The first case above is when we pop the top of the monotonic stack, so we should add one to the position of the top person in the stack before we pop him. The second case is when we push. Before we push a person, all other person shorter must be popped already since we’re maintaining a monotonic descreasing stack, so when we can push, there must be no other person who is taller than our top and the person we push, which matches the definition of the second case above.

Below is the code.

 1class Solution {
 2public:
 3    vector<int> canSeePersonsCount(vector<int>& heights) {
 4        stack<int> st;
 5        int H = heights.size();
 6        vector<int> ans(H);
 7        for (int i=0; i<H; i++) {
 8            while (st.size() and heights[st.top()] < heights[i]) {
 9                ans[st.top()]++;
10                st.pop();
11            }
12            if (st.size()) ans[st.top()]++;
13            st.push(i);
14        }
15        return ans;
16    }
17};