6 Similar questions || Prev smaller - Next smaller || Monotonic stack || C++
1. Largest Rectangle in a Histogram: https://leetcode.com/problems/largest-rectangle-in-histogram/\n\n\nclass Solution {\npublic:\n    int largestRectangleArea(
**1. Largest Rectangle in a Histogram**: https://leetcode.com/problems/largest-rectangle-in-histogram/\n\n```\nclass Solution {\npublic:\n    int largestRectangleArea(vector<int>& heights) {\n        int n = heights.size();\n        vector<int> nsl(n),psl(n);\n        \n        stack<int> s;\n        \n        for(int i=n-1;i>=0;i--){\n            while(!s.empty() && heights[s.top()]>=heights[i]){\n                s.pop();\n            }\n            nsl[i] = s.empty() ? n : s.top();\n            s.push(i);\n        }\n        \n        while(!s.empty()){\n            s.pop();\n        }\n        \n        for(int i=0;i<n;i++){\n            while(!s.empty() && heights[s.top()]>=heights[i]){\n                s.pop();\n            }\n            psl[i] = s.empty() ? -1: s.top();\n            s.push(i);\n        }\n        \n        int ans = INT_MIN;\n        for(int i=0;i<n;i++){\n            ans = max(ans,(nsl[i]-psl[i]-1)*(heights[i]));\n        }\n        \n        return ans;\n    }\n};\n\n```\n\n**2. Maximal Rectangle** : https://leetcode.com/problems/maximal-rectangle/\n\n```\nclass Solution {\npublic:\n    \n    \n    int histogram(vector<int>& heights){\n        int n = heights.size();\n        vector<int> nsl(n),psl(n);\n        \n        stack<int> s;\n        \n        for(int i=n-1;i>=0;i--){\n            while(!s.empty() && heights[s.top()]>=heights[i]){\n                s.pop();\n            }\n            nsl[i] = s.empty() ? n : s.top();\n            s.push(i);\n        }\n        \n        while(!s.empty()){\n            s.pop();\n        }\n        \n        for(int i=0;i<n;i++){\n            while(!s.empty() && heights[s.top()]>=heights[i]){\n                s.pop();\n            }\n            psl[i] = s.empty() ? -1: s.top();\n            s.push(i);\n        }\n        \n        int ans = INT_MIN;\n        for(int i=0;i<n;i++){\n            ans = max(ans,(nsl[i]-psl[i]-1)*(heights[i]));\n        }\n        \n        return ans;\n    }\n    \n    \n    \n    \n    \n    \n    int maximalRectangle(vector<vector<char>>& matrix) {\n        \n        \n        \n        int n = matrix.size();\n        \n        if(n==0){\n            return 0;\n        }\n        \n        \n        int m = matrix[0].size();\n        \n        int dup[n][m];\n        \n        for(int i=0;i<n;i++){\n            for(int j=0;j<m;j++){\n                if(matrix[i][j]==\'0\'){\n                    dup[i][j]=0;\n                }\n                else{\n                    dup[i][j]=1;\n                }\n            }\n        }\n        \n\n        for(int i=0;i<n;i++){\n            if(i==0) continue;\n            \n            for(int j=0;j<m;j++){\n                if(matrix[i][j]==\'1\'){\n                    dup[i][j] = 1+dup[i-1][j];\n                }\n                else{\n                    dup[i][j] = 0;\n                }\n            }\n        }\n        \n        \n        int ans = INT_MIN;\n        \n        for(int i=0;i<n;i++){\n            vector<int> each_row;\n            for(int j=0;j<m;j++){\n                each_row.push_back(dup[i][j]);\n            }\n            \n            ans = max(ans,histogram(each_row));\n        }\n        \n        \n        return ans;\n    }\n};\n\n```\n\n**3. Maximum score of a Good subarray**: https://leetcode.com/problems/maximum-score-of-a-good-subarray/\n\n```\nclass Solution {\npublic:\n    int maximumScore(vector<int>& nums, int k) {\n        int n=nums.size();\n        int ans=0;\n        vector<long long>nsr(n),nsl(n);\n        //NSL\n        stack<int>st;\n        for(int i=0;i<n;i++){\n            while(!st.empty() && nums[st.top()]>=nums[i])\n                st.pop();\n            nsl[i]=st.empty()?-1:st.top();\n            st.push(i);\n        }\n        //NSR\n        stack<int>tt;\n        for(int i=n-1;i>=0;i--){\n            while(!tt.empty() && nums[tt.top()]>=nums[i])\n                tt.pop();\n            nsr[i]=tt.empty()?n:tt.top();\n            tt.push(i);\n        }\n        vector<long long>pref(n,0);\n        pref[0]=nums[0];\n        \n        for(int i=1;i<n;i++){\n            pref[i]=pref[i-1]+nums[i];\n        }\n        \n        for(int i=0;i<n;i++){\n            int mn = nums[i];\n            int l=nsl[i]+1, r=nsr[i]-1;\n            int len, prod;\n            if(l<=k && r>=k){\n                len = r-l+1;\n                prod = mn*len;\n                ans = max(ans,prod);\n            }\n            \n        }\n        return ans;\n    }\n};\n```\n\n**4. Sum of subarray minimums** : https://leetcode.com/problems/sum-of-subarray-minimums/\n\n```\nclass Solution {\npublic:\n    int sumSubarrayMins(vector<int>& arr) {\n        \n        int mod = 1000000007;\n        int n = arr.size();\n        vector<int> nsl(n);\n        vector<int> psl(n);\n        \n        stack<int> s;\n        \n        for(int i=n-1;i>=0;i--){\n            while(!s.empty() && arr[s.top()]>arr[i]){\n                s.pop();\n            }\n            nsl[i] = s.empty() ? n : s.top();\n            s.push(i);\n        }\n        \n        while(!s.empty()){\n            s.pop();\n        }\n        \n        for(int i=0;i<n;i++){\n            while(!s.empty() && arr[s.top()]>=arr[i]){\n                s.pop();\n            }\n            psl[i] = s.empty() ? -1: s.top();\n            s.push(i);\n        }\n        \n        long long ans = 0;\n        for(int i=0;i<n;i++){\n            long long r = nsl[i]-i;\n            long long l = i-psl[i];\n            \n            cout<<psl[i]<<" "<<nsl[i]<<endl;\n            \n            ans+= (l*r*arr[i]);\n            ans = ans%mod;\n        }\n        \n        return ans;\n    }\n};\n```\n\n**5. Maximum subarray min-Product**: https://leetcode.com/problems/maximum-subarray-min-product/\n\n```\nclass Solution {\npublic:\n    int maxSumMinProduct(vector<int>& nums) {\n        int n = nums.size();\n        \n        vector<int> nsl(n);\n        vector<int> psl(n);\n        \n        int mod = 1000000007;\n        \n        \n        stack<int> s;\n        for(int i=n-1;i>=0;i--){\n            while(!s.empty() && nums[s.top()]>=nums[i]){\n                s.pop();\n            }\n            nsl[i] = s.empty() ? n: s.top();\n            s.push(i);\n        }\n        \n        while(!s.empty()){\n            s.pop();\n        }\n        \n        for(int i=0;i<n;i++){\n            while(!s.empty() && nums[s.top()]>=nums[i]){\n                s.pop();\n            }\n            psl[i] = s.empty() ? -1: s.top();\n            s.push(i);\n        }\n        \n        long long prefix[n+1];\n        prefix[0]=0;\n        for(int i=1;i<=n;i++){\n            prefix[i] = prefix[i-1]+nums[i-1];\n        }\n        \n        long long ans = INT_MIN;\n        for(int i=0;i<n;i++){\n            ans = max(ans,nums[i]*(prefix[nsl[i]]-prefix[psl[i]+1]));\n        }\n        \n        return ans%mod;\n        \n    }\n};\n\n```\n\n**6. Daily Temperatures**: https://leetcode.com/problems/daily-temperatures/\n\n```\nclass Solution {\npublic:\n    vector<int> dailyTemperatures(vector<int>& temperatures) {\n        stack<int> s;\n        \n        int n = temperatures.size();\n        \n        vector<int> ans(n);\n        \n        for(int i=n-1;i>=0;i--){\n            if(s.empty()){\n                ans[i] = 0;\n            }\n            else{\n                while(!s.empty() && temperatures[i]>=temperatures[s.top()]){\n                    s.pop();\n                }\n                \n                if(s.empty()){\n                    ans[i] = 0;\n                }\n                else{\n                    ans[i] = s.top()-i;\n                }\n                \n                \n            }\n            \n            s.push(i);\n        }\n        \n        \n        return ans;\n    }\n};\n\n```\n\n
['C', 'Monotonic Stack']