Monotonic stack vs DP||37ms Beats 99.98%
Intuition\n Describe your first thoughts on how to solve this problem. \nThe same method can generalized to solve 85. Maximal Rectangle\n\n2 approaches are prov
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe same method can generalized to solve [85. Maximal Rectangle](https://leetcode.com/problems/maximal-rectangle/solutions/5014468/monotonic-stackdpcount-successive-1s16ms-beats-9962/)\n\n2 approaches are provided. The monotonic stack method is 1-pass. DP method is a 2-pass method.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe part for monotonic stack is almost the same like in solving Leetcode 85. Maximal Rectangle which is harder.\n\nThe pattern for monotonic stack is used for many Leetcode\'s hard questions for which the variant is applied to LC 84 & LC 85 as follows (using C-style)\n```\nst={-1}; //let stack contain an element -1\ntop=0;\nfor (r=0; r<=col; r++){//Moving right index\n    // Count the successive \'1\'s & store in h[j]\n    h[j]=compute_for_h(j);\n\n    // monotonic stack has at least element -1\n    while(st has more than -1 and (j==col or h[j]<h[st[top]])){\n        m=st[top--];//pop\n        l=st[top];//left index\n        w=r-l-1;\n        area=h[m]*w;\n        maxArea=max(maxArea, area);\n    }\n    st[++top]=j;//push\n}\n```\n\nThe following is generated by random data to show the maxArea for the histogram `h`. The green area is in fact the cells with \'1\' which are connected to the cells \'1\' in the row for considering.\n![hist_maxArea.png](https://assets.leetcode.com/users/images/2bd2c140-882b-4394-b43b-325ff1b7f92a_1712987673.8139648.png)\n[Please turn on english subtitles. Solving [42. Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/solutions/5010020/monotonic-stack-vs-priority-queueusing-pyplot-explain3ms-beats-9910/) use a similar way of monotonic stack, in the film is shown how to use pyplot.bar to visualize the data, especially for the area computing.]\n[https://youtu.be/IERpc-YJIT0?si=HaXCPOHz83goH3yf](https://youtu.be/IERpc-YJIT0?si=HaXCPOHz83goH3yf)\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n# Code using monotonic stack||37ms Beats 99.98%\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    int largestRectangleArea(vector<int>& heights) {\n        if (heights.size()==0) return 0;\n        heights.push_back(0);// easy for removing if-branch\n        const int n=heights.size();\n        int maxA=0;\n        vector<int> st={-1};\n        for(int r=0; r<n; r++){\n            while(st.size()>1 && heights[st.back()]>=heights[r]){\n                const int m=st.back();\n                st.pop_back();\n                const int w=r-st.back()-1;\n                const int area=heights[m]*w;\n                maxA=max(maxA, area);\n            }\n            st.push_back(r);\n        }\n        return maxA;\n    }\n};\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n# C++ using DP||45ms Beats 99.88%\n\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    //l: the x-coordinate of the bar to the left with height h[l] < h[i].\n    //r: the x-coordinate of the bar to the right with height h[r] < h[i].\n    int largestRectangleArea(vector<int>& heights) {\n        const int n=heights.size();\n        if (heights.size()==0) return 0;\n        vector<int> l(n),  r(n);\n        r[n-1]=n, l[0]=-1;\n\n        for(int i=1; i<n; i++){\n            int p=i-1;\n            while(p>=0 && heights[p]>=heights[i])\n                p=l[p];\n            l[i]=p;\n        }\n\n        int maxA=heights[n-1]*(r[n-1]-l[n-1]-1);\n        for(int i=n-2; i>=0; i--){\n            int p=i+1;\n            while(p<n && heights[p]>=heights[i])\n                p=r[p];\n            r[i]=p;\n            maxA=max(maxA, heights[i]*(r[i]-l[i]-1));\n        }\n        return maxA;\n    }\n};\n```
['Dynamic Programming', 'Monotonic Stack', 'C++']