Easy understanding solution with monotonic stack C++ (image explanation included)
Intuition\n Describe your first thoughts on how to solve this problem. \nTry to find the longest width w.r.t. height[i], which means we have to find the most le
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTry to find the longest width w.r.t. `height[i]`, which means we have to find the most left (called `start`) and right (called `end`) positions where the all the heights between `[start, end]` are greater or equal to `height[i]`.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nUsing monotonic stack to find the first lower element in both left and right directions. If the index of the first lower element is `l`, it means from position `l + 1` to current position `i`, all the heights are greater or equal to current height `height[i]`. This is same for the right direction.\nAfter we find the first lower element in left (called `start`) and right(called `end`) directions, the width of this rectangle is `end - start + 1`, for each height, we can calculate the area respectively.\n![image.png](https://assets.leetcode.com/users/images/62f1d0d4-f979-4008-a37d-59c18bd6e3e3_1703122099.7591784.png)\n\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nWhile building `starts` and `ends` and calculating the `max_area`, we traverse each element at most once.\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe `starts` and `ends` have the same size as `heights`.\n\n# Code\n```\nclass Solution {\npublic:\n    int largestRectangleArea(vector<int>& heights) {\n        int max_area = 0;\n        int n = heights.size();\n        vector<int> starts(n, 0);\n        vector<int> ends(n, 0);\n        \n        stack<int> st;\n        // Step 1: find the `start` for each height using monotonic stack.\n        for (int i = n - 1; i >= 0; i--) {\n            while (!st.empty() && heights[st.top()] > heights[i]) {\n                starts[st.top()] = i + 1;\n                st.pop();\n            };\n            st.push(i);\n        }\n\n        while(!st.empty()) {\n            starts[st.top()] = 0;\n            st.pop();\n        }\n\n        // Step 2: find the `end` for each height using monotonic stack.\n        for (int i = 0; i < n; i++) {\n            while (!st.empty() && heights[st.top()] > heights[i]) {\n                ends[st.top()] = i - 1;\n                st.pop();\n            };\n            st.push(i);\n        }\n\n        while(!st.empty()) {\n            ends[st.top()] = n - 1;\n            st.pop();\n        }\n\n        // Step 3: calcuate the area for each height.        \n        for (int i = 0; i < n; i++) {\n            int width = ends[i] - starts[i] + 1;\n            max_area = max(max_area, heights[i] * width);\n        }\n        return max_area;\n    }\n};\n```
['Greedy', 'Monotonic Stack', 'C++']