O(n) solution with clear code
The idea is very simple: for each bar find the area of the rectangle where this bar height defines the height of the whole rectangle.\nTo do that in O(n), we ne
The idea is very simple: for each bar find the area of the rectangle where this bar height defines the height of the whole rectangle.\nTo do that in O(n), we need to find in O(1) the following indices:\n\t1) Index of the first element on the left from current `i` which is smaller than `heights[i]`\n\t2) Index of the first element on the right from current `i` which is smaller than `heights[i]`\n\n```C++\n    vector<int> getNextSmaller(const vector<int>& heights) {\n        stack<int> st;\n        vector<int> res(heights.size(), heights.size());\n        for (int i = 0; i < heights.size(); ++i) {\n            while (!st.empty() && heights[st.top()] > heights[i]) {\n                res[st.top()] = i;\n                st.pop();\n            }\n            st.push(i);\n        }\n        \n        return res;\n    }\n    // exactly the same as above except for the order\n    // and the default element here is -1 (assume the the smaller element is before the start of the array)\n    vector<int> getPrevSmaller(const vector<int>& heights) {\n        stack<int> st;\n        vector<int> res(heights.size(), -1);\n        for (int i = heights.size() - 1; i >= 0; --i) {\n            while (!st.empty() && heights[st.top()] > heights[i]) {\n                res[st.top()] = i;\n                st.pop();\n            }\n            st.push(i);\n        }\n        \n        return res;\n    }\n    \n    int largestRectangleArea(vector<int>& heights) {\n        if (heights.size() == 0) return 0;\n        \n        auto nextSmaller = getNextSmaller(heights);\n        auto prevSmaller = getPrevSmaller(heights);\n        \n        int res = 0;\n        for (int i = 0; i < heights.size(); ++i) {\n            int r = nextSmaller[i];\n            int l = prevSmaller[i];\n            res = max(res, heights[i]*(r - l - 1));\n        }\n        \n        return res;\n    }\n```
['C']