[C++] O(n) Stack solution || Explaination with diagram
Approach:\nArea of reactangle is height * width\nSince we want to maximise the area , we can either increase height or width. But since the heights are already 
**Approach:**\nArea of reactangle is height * width\nSince we want to maximise the area , we can either increase height or width. But since the heights are already fixed , we need to find the maximum width for each height,\n\nThe naive approach to implement this is to traverse and for each height traverse to left and right and find the first block shorter than current . If we go beyond this , then we can form a rectangle only by \ntaking height of smaller block. \n**Time**: O(n^2), **Space**: O(1)\n\n**Optimisation**:\nWe can optimise the time to find smaller block on both sides by using a monotonic stack.\n1. We traverse from left and right seperately. \n2. The idea of monotonic stack is simple , if we find a smaller element than those in stack, then simply pop those greater elements from stack as if the new element is smaller than them , then it would be the first to cause any hinderance to further element and the elements in stack would be useless \n3. While doing so store the values in left and right arrays.\n4. Now traverse in array and now we can find left and right smaller blocks in constant time\n\n**Time: O(n)\nSpace: O(n)**\n\n![image](https://assets.leetcode.com/users/images/5e3d3d9a-36de-471c-81f9-08c5d92e4524_1643433903.9594283.png)\n\n\n```\nclass Solution {\npublic:\nint largestRectangleArea(vector<int>& heights) {\n    int n = heights.size();\n    vector<int> left(n, 0) , right(n, 0);\n\n    stack<int> s;\n\n    for (int i = 0; i < n; i++) {\n        while (!s.empty() and heights[s.top()] >= heights[i]) {\n            s.pop();\n        }\n        left[i] = (s.empty()) ? -1 : s.top();\n        s.push(i);\n    }\n\n    while (!s.empty())\n        s.pop();\n\n    for (int i = n - 1; i >= 0; i--) {\n        while (!s.empty() and heights[s.top()] >= heights[i]) {\n            s.pop();\n        }\n        right[i] = (s.empty()) ? n : s.top();\n        s.push(i);\n    }\n\n    int ans = INT_MIN;\n\n    for (int i = 0; i < n; i++) {\n        int distance = right[i] - left[i] - 1;\n        ans = max(ans , heights[i] * distance);\n    }\n\n\n    return ans;\n\n}\n};\n```
['Monotonic Stack']