✔ C++ || 💯 Explanation using Stack || O(N) time, space
Problem:\n- We are given an array of integers which represent the height of bars in a histogram.\n- The width of each bar is 1.\n- We need to form a rectangle w
Problem:\n- We are given an array of integers which represent the height of bars in a histogram.\n- The width of each bar is 1.\n- We need to form a rectangle with these bars with the largest area.\n\nExample :\n\n![WhatsApp Image 2023-04-20 at 10.54.15 AM.jpeg](https://assets.leetcode.com/users/images/f503d54d-30ce-43b4-80a1-781f6ef109d9_1681968701.6486282.jpeg)\n\n\n- Above we have a histogram, where value of bar represents the height of the bar.\n- We need to form rectangle using these which has the largest area.\n- Say, one rectangle which can be formed would be of ```height = 1```, and ```width = 6```, like below :\n\n![3_1.jpeg](https://assets.leetcode.com/users/images/9effc917-9fc9-4388-827d-2a396a4dca7d_1681968812.4244616.jpeg)\n\n\n- Another rectangle which can be formed is using the last 4 bars, as shown below:\n\n![2_1.jpeg](https://assets.leetcode.com/users/images/f0e78d03-49da-48ed-a9cc-c64d6ba8553f_1681968839.778373.jpeg)\n\n\n- Since we need to find the rectangle with the largest area, it would be the one below : \n\n![4_1.jpeg](https://assets.leetcode.com/users/images/67aaa468-39bb-4ebc-aacd-70b31e37151e_1681968868.5627692.jpeg)\n\n\n# Solution explaination:\n\n- So the idea is to use stack, in such a way, that we push the indexes of bars with increasing heights into it.\n- If, at one point, we find a bar smaller than the bar in the top of stack, we will pop that bar, and use it as height of rectangle, and the width would be the the difference between the index of the popped bar and the index of the bar which we are currently at. \n- Let\'s understand through an example : ```[ 1 , 2 , 3 , 1]```\n\n![5_1.jpeg](https://assets.leetcode.com/users/images/b359e6d3-41ef-44c6-9862-52fe2f930924_1681968900.60353.jpeg)\n\n\n- We will iterate through the bars one by one, through a variable, say ```i```. \n- Also, lets make a stack, initially empty.\n\n![6_1.jpeg](https://assets.leetcode.com/users/images/b64775a5-d308-4d02-9c59-03bb80ad39a5_1681968924.4549932.jpeg)\n\n\n- At , ```i = 0```, our stack is initially empty, so we push the index , ```i = 0``` into stack, and increment ```i```.\n\n![7_1.jpeg](https://assets.leetcode.com/users/images/13b0be3f-dde6-4471-9baa-d6138ee78340_1681968947.7664087.jpeg)\n\n\n- At, ```i = 1```, our stack is not empty.\n- As I had said, we will be pushing bars into stack, if the bar at which we are currently at (i = 1) is greater than the bar at the top of stack.\n- ```Top of stack = 0 , height[0] = 1```\n- ``` i = 1 , height [1] = 2 ```\n- ``` Since height[i] >= height[top of stack],therefore, push i=1 into stack```\n\n![8_1.jpeg](https://assets.leetcode.com/users/images/377721c8-91f2-4b71-b602-846cabe52881_1681968974.5572207.jpeg)\n\n\n- Similary, at ```i = 2``` \n-  ```Top of stack = 1 , height[1] = 2```\n- ``` i = 2 , height [2] = 3 ```\n- ``` Since height[i] >= height[top of stack],therefore, push i = 2 , into stack```\n\n![9_1.jpeg](https://assets.leetcode.com/users/images/9e089954-6f87-4518-a955-d31933284a84_1681968992.3227355.jpeg)\n\n\n- Now, at ``` i = 3 ``` , we see that ```height[i] < height[top of stack]```\n- ```height[i] = height[3] = 1```\n- ```height[top of stack] = height[2] = 3```\n- So, we cannot push this bar into stack.\n- We pop out the index at the top of the stack.\n- Now using this bar, we will form the ```height``` of rectangle.\n- So the question to form the ```width``` rectangle is : \n```\n What is the distance between the bars , top of stack, \n and the index \'i\' ?\n  \n```\n- Important idea to note is, that while forming rectangle, we do not consider merging the bars behind the top of stack bar\n- This is because we have pushed them into the stack.Meaning they must already be less than this bar, so we cannot merge them with this bar to form rectangle.\n- So, we can can calculate our ```height``` and ```width``` of rectangle, and then calculate the area as shown below:\n\n![10_1.jpeg](https://assets.leetcode.com/users/images/b72f0f05-a458-4aa8-8a31-3e85ab4c4336_1681969035.2992516.jpeg)\n\n\n![11_1.jpeg](https://assets.leetcode.com/users/images/394663b8-f9d3-4046-b112-23e415e8df18_1681969084.0234222.jpeg)\n\n\n![12_1.jpeg](https://assets.leetcode.com/users/images/e4a6e6b4-ba38-402d-92d9-c5937929d85a_1681969102.8191037.jpeg)\n\n![13_1.jpeg](https://assets.leetcode.com/users/images/7706ad12-cb1d-42d1-a0b4-d9fde690e55d_1681969113.2921057.jpeg)\n\n- So , our ```max area = 3 ``` so far.\n- Again , we will compare the ```height[i]``` bar and ```height[top of stack]``` bar.\n- ```height[i] = height[3] = 1```\n- ```height[top of stack] = height[1] = 2```\n- Since ```height[i] <= height[top of stack] ``` we will pop from the stack, as shown below :\n\n![14_1.jpeg](https://assets.leetcode.com/users/images/74149e41-3a69-4e4d-ba76-f0d48322c580_1681969141.1497586.jpeg)\n\n\n- We will try forming a rectangle with ```height = height[top of stack] ```. \n\n![15_1.jpeg](https://assets.leetcode.com/users/images/06128f91-54bc-4ff6-a038-cf46e6447034_1681969167.3417048.jpeg)\n\n\n![16_1.jpeg](https://assets.leetcode.com/users/images/3cc847dd-b3f1-4d7f-85c1-b12ad551f836_1681969191.2273915.jpeg)\n\n\n- The area formed = 4, which is greater than ```max area = 3``` therefore, we will update ```max area = 4``` now.\n- Again, we will compare with ```height[i]``` and ```height[top of stack]```.\n- ```height[i] = height[3] = 1```\n- ```height[top of stack] = height[0] = 1 ```\n- ```height[i] <= height[top of stack]```, therefore pop from stack.\n\n![17_1.jpeg](https://assets.leetcode.com/users/images/8023ad8b-42f6-4ea6-9a87-5f2511393ecc_1681969216.411232.jpeg)\n\n\n![t_345.jpeg](https://assets.leetcode.com/users/images/df819cfc-90be-48ad-8235-787138fc1470_1681972523.8587441.jpeg)\n\n\n![t_234.jpeg](https://assets.leetcode.com/users/images/245a0e3a-bfaa-4cd1-831f-280578ccb17d_1681973020.3200893.jpeg)\n\n\n- We have an empty stack, so we will push ```i=3``` bar into stack and increment ``i``.\n\n![t_182.jpeg](https://assets.leetcode.com/users/images/03b6741c-017d-4ddb-a83f-fc3013296596_1681972764.2276301.jpeg)\n\n\n- Since, we have tarversed all the bars, ```i=4```, there is no need to push more bars into the stack.\n- However, our stack is not yet empty.\n- So we will pop out the top of stack, and use it as ```height``` of rectangle.\n- So,\n\n\n![t_111.jpeg](https://assets.leetcode.com/users/images/259321da-5a11-485a-b5a4-a59a81358eb0_1681972640.717916.jpeg)\n\n\n![21_1.jpeg](https://assets.leetcode.com/users/images/cad162ee-9ae2-4932-b4cd-150f3698d22c_1681969371.0752761.jpeg)\n\n\n- ```Thus the rectangle which can be formed with the max area would be = 4```.\n\n\n\n\n\n\n```\nclass Solution {\npublic:\n    int largestRectangleArea(vector<int>& heights) {\n        stack<int>stk;\n        int i=0;\n        int n=heights.size();\n        int maxArea = 0;\n        while(i < n)\n            {   \n\n    if(stk.empty() or( heights[stk.top()] <= heights[i] ))\n            {\n                stk.push(i++);\n            }\n            else\n            {\n                int minBarIndex = stk.top();\n                stk.pop();\n                int width = i;\n                if(!stk.empty())  width = i - 1 - stk.top();\n                int area = heights[minBarIndex] * width;\n                maxArea = max(maxArea , area);\n            }\n        }\n\n        while(!stk.empty())\n        {\n            int minBarIndex = stk.top();\n            stk.pop();\n            int width = i;\n            if(!stk.empty())  width = i - 1 - stk.top();\n            int area = heights[minBarIndex] * width;\n            maxArea = max(maxArea , area);\n        }\n        return maxArea;\n    }\n};\n```
['Stack', 'Monotonic Stack', 'Simulation', 'C++']