Solution

Method 1 – Monotonic Stack for Each Row and Column

Intuition

For each person, we need to count how many people they can see to the right and below, following the rule that all people in between must be shorter than both. This is a classic monotonic stack problem, similar to "next greater element" but counting visible people.

Approach

For each row, process from right to left using a stack:
- For each person, pop from the stack while the top is shorter than the current person, counting each pop as a visible person.
- If the stack is not empty after popping, the next person is also visible.
Repeat for each column, processing from bottom to top.
Sum the counts for each person.
Return the answer grid.

Code

[{"language":"C++","code":"#include <vector>\n#include <stack>\nusing namespace std;\nclass Solution {\npublic:\n    vector<vector<int>> canSeePersons(vector<vector<int>>& heights) {\n        int m = heights.size(), n = heights[0].size();\n        vector<vector<int>> ans(m, vector<int>(n, 0));\n        // Right direction\n        for (int i = 0; i < m; ++i) {\n            stack<int> st;\n            for (int j = n-1; j >= 0; --j) {\n                int cnt = 0;\n                while (!st.empty() && heights[i][j] > heights[i][st.top()]) {\n                    st.pop(); ++cnt;\n                }\n                if (!st.empty()) ++cnt;\n                ans[i][j] += cnt;\n                st.push(j);\n            }\n        }\n        // Down direction\n        for (int j = 0; j < n; ++j) {\n            stack<int> st;\n            for (int i = m-1; i >= 0; --i) {\n                int cnt = 0;\n                while (!st.empty() && heights[i][j] > heights[st.top()][j]) {\n                    st.pop(); ++cnt;\n                }\n                if (!st.empty()) ++cnt;\n                ans[i][j] += cnt;\n                st.push(i);\n            }\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">#include</span><span style=\"color:#032F62;--shiki-dark:#9ECBFF\"> &#x3C;vector></span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">#include</span><span style=\"color:#032F62;--shiki-dark:#9ECBFF\"> &#x3C;stack></span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">using</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> namespace</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> std</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">;</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark

Related Tags