NO STACK used, only vector!!
Intuition \n Describe your first thoughts on how to solve this problem. \nSee this problem is little (un-intuitive) but pure logic. Just focus on the pattern of
# Intuition \n<!-- Describe your first thoughts on how to solve this problem. -->\nSee this problem is little (un-intuitive) but pure logic. Just focus on the pattern of given a height value at some position i, is the (i + 1)th position is bigger/equal or smaller than the current value.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nApproach of this question is based on a simple intuition mentioned above and thus bifurcate in 2 cases.\n\n1. if a value smaller than the current value appear next in array then max-height of rectangle that can be formed with all future values will be limited by the smaller one. \nEg :- 2 1 5 6 ...\nat first we encounter 2, so 2 can expand only if next number is >= 2,\nbut its 1 so 2\'s ability is nerfed by 1, and 1 will take the place of 2, meaning if a new number 5 comes, it can form rectangle upto 2\'s place with height 1. So 1 replace everything that is bigger than its value that is already encountered.\n\n2. if number that comes next is bigger or equal to current that we just put its value and position.\n\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\n\nclass Solution {\npublic:\n    int largestRectangleArea(vector<int>& h) {\n        int n = h.size(), ans = h[0];\n        vector<vector<int>> v;\n        v.push_back({h[0], 0});\n        for(int i = 1; i < n; i++)\n        {\n            if(h[i] > v[v.size() - 1][0]) v.push_back({h[i], i});\n            else\n            {\n                int x;\n                while(v.size() && v[v.size() - 1][0] >= h[i])\n                {\n                    ans = max(ans, v[v.size() - 1][0] * (i - v[v.size() - 1][1]));\n                    x = v[v.size() - 1][1];\n                    v.pop_back();\n                }\n                v.push_back({h[i], x});\n            }\n        } \n\n        while(!v.empty())\n        {\n            ans = max(ans, v[v.size() - 1][0] * (n - v[v.size() - 1][1]));\n            v.pop_back();\n        }\n\n        return ans;\n    }\n};\n```
['C++']