C++ stack solution
The idea is simple: suppose a rectangle contains the column i and has a height heights[i], then the max area of the rectangle will be heights[i] * (rb[i] - lb[i
The idea is simple: suppose a rectangle contains the column `i` and has a height `heights[i]`, then the max area of the rectangle will be `heights[i] * (rb[i] - lb[i] - 1)`. Here we define:\n\n- `lb[i]`: the index of first column on the left of `i` whose height is lower than `heights[i]`.\n- `rb[i]`: the index of first column on the right of `i` whose height is lower than `heights[i]`.\n\nWe first scan the `heights` array and use a stack to construct `lb[i]` and `rb[i]`. After that, we scan `heights` again and calculate  `heights[i] * (rb[i] - lb[i] - 1)` to get the max possible area.\n\n```\nclass Solution {\npublic:\n    int largestRectangleArea(vector<int>& heights) {\n        int N = heights.size();\n        stack<int> st;\n        // construct lb[i]: idx of first col on the left that is lower than height[i]\n        vector<int> lb(N);\n        for (int i(0); i < N; ++i) {\n            while (!st.empty() and heights[st.top()] >= heights[i]) {\n                st.pop();\n            }\n            if (st.empty()) {\n                lb[i] = -1;\n                st.push(i);\n            }\n            else {\n                lb[i] = st.top();\n                st.push(i);\n            }\n        }\n        \n        // clear stack\n        while (!st.empty()) st.pop();\n        \n        // construct rb[i]: idx of first col on the right that is lower than height[i]\n        vector<int> rb(N);\n        for (int i(N-1); i >= 0; --i) {\n            while (!st.empty() and heights[st.top()] >= heights[i]) {\n                st.pop();\n            }\n            if (st.empty()) {\n                rb[i] = N;\n                st.push(i);\n            }\n            else {\n                rb[i] = st.top();\n                st.push(i);\n            }\n        }\n        \n        // scan each col and get max area\n        int rst = 0;\n        for (int i(0); i < N; ++i) {\n            rst = max(rst, \n                     heights[i] * (rb[i] - lb[i] - 1)\n                     );\n        }\n        return rst;\n    }\n};\n```
['C++']