Must Read Monotonic Stack Pattern - Variations
Introduction To stack and NEG pattern - 4 variations covered in\n\n232. Implement Queue using Stacks\n225. Implement Stack using Queues\n155. Min Stack\n496. Ne
Introduction To stack and NEG pattern - **4 variations** covered in\n\n[232. Implement Queue using Stacks](https://leetcode.com/problems/implement-queue-using-stacks/solutions/5203561/implement-queue-using-stacks/)\n[225. Implement Stack using Queues](https://leetcode.com/problems/implement-stack-using-queues/solutions/5203563/implement-stacks-using-queue/)\n[155. Min Stack](https://leetcode.com/problems/min-stack/solutions/4185675/java-simple-solution-using-two-stack-and-one-stack/)\n[496. Next Greater Element I](https://leetcode.com/problems/next-greater-element-i/solutions/5164552/must-read-intuitive-pattern-for-deep-understanding-of-nge-and-nsm/) **very very important**\n[503. Next Greater Element II](https://leetcode.com/problems/next-greater-element-ii/solutions/5201809/brute-intuitive-solution-beats-98-monotonic-pattern/)\n[907. Sum of Subarray Minimums](https://leetcode.com/problems/sum-of-subarray-minimums/solutions/5165808/monotonic-patter-continuation/) **pattern**\n[11. Container With Most Water](https://leetcode.com/problems/container-with-most-water/solutions/5165076/must-read-maximum-water-pattern/)\n[42. Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/solutions/5165626/building-intuitive-solution-one-step-at-a-time/)\n[1856. Maximum Subarray Min-Product](https://leetcode.com/problems/maximum-subarray-min-product/solutions/5167159/must-read-monotonic-stack-pattern-variations/)\n[735. Asteroid Collision](https://leetcode.com/problems/asteroid-collision/solutions/5166334/brute-solution/)\n[402. Remove K Digits](https://leetcode.com/problems/remove-k-digits/solutions/5166502/beast-intuitive-approach-step-by-step-nsg-to-right/)\n[2104. Sum of Subarray Ranges](https://leetcode.com/problems/sum-of-subarray-ranges/solutions/5166891/beastt-solution/)\n[84. Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/solutions/5172029/monotonic-stack-pattern-deep-understanding/)\n[85. Maximal Rectangle](https://leetcode.com/problems/maximal-rectangle/solutions/5201947/brute-intuitive-solution-beats-98-monotonic-stack-pattern-deep-understanding/)\n[739. Daily Temperatures](https://leetcode.com/problems/daily-temperatures/solutions/5167031/must-read-monotonic-stack-pattern-variations/) **Fundamental**\n[853. Car Fleet](https://leetcode.com/problems/car-fleet/solutions/5167204/must-read-monotonic-stack-pattern-variations/)\n[150. Evaluate Reverse Polish Notation](https://leetcode.com/problems/evaluate-reverse-polish-notation/solutions/5172161/stack-intuitive-solution/)\n[895. Maximum Frequency Stack](https://leetcode.com/problems/maximum-frequency-stack/solutions/5172171/stack-implementation-problem/) **VVI** Implementation problem\n[173. Binary Search Tree Iterator](https://leetcode.com/problems/binary-search-tree-iterator/solutions/5172179/brute-solution/)\n[682. Baseball Game](https://leetcode.com/problems/baseball-game/solutions/5172183/straight-forward-approach/)\n[1209. Remove All Adjacent Duplicates in String II](https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/solutions/5172210/stack-solution-pattern/) **Must Go through**\n[456. 132 Pattern](https://leetcode.com/problems/132-pattern/solutions/5202876/monotonic-stack/)\n[22. Generate Parentheses](https://leetcode.com/problems/generate-parentheses/solutions/5202882/monotonic-stack/)\n[460. LFU Cache]()\n[146. LRU Cache]()\n[901. Online Stock Span](https://leetcode.com/problems/online-stock-span/solutions/5172217/stack-nge-and-nse-deep-understanding/) **Must Read**\n[239. Sliding Window Maximum](https://leetcode.com/problems/sliding-window-maximum/solutions/5175931/nge-pattern/) **All three solution**\n[856. Score of Parentheses](https://leetcode.com/problems/score-of-parentheses/solutions/5203496/scoreofparentheses/)\n[844. Backspace String Compare](https://leetcode.com/problems/backspace-string-compare/solutions/5203544/brute-and-optimized-backspacecompare-beats-100/)\n[71. Simplify Path](https://leetcode.com/problems/simplify-path/solutions/5203538/simplifypath/)\n\n<br/>\n\n<br/>\n\n# Code\n```java []\nclass Solution {\n    \n    private static final int MOD = (int)(1e9+7);\n    \n    public int maxSumMinProduct(int[] nums) {\n        long res = 0;\n        Stack<Pair> stack = new Stack<>();\n        int n = nums.length;\n        long[] prefix = new long[n + 1];//prefixSum will contain the sum of subArray till that index.\n        \n        // Compute the prefix sums\n        for (int i = 0; i < nums.length; i++) {\n            prefix[i + 1] = prefix[i] + nums[i];\n        }\n        \n        // Traverse through the nums array\n        for (int i = 0; i <= n; i++) {\n            int newStart = i;\n            \n            while (!stack.isEmpty() && (i==n||stack.peek().value > nums[i])) {// NOTE NEXT SMALLEST ELEMENT CONDITION\n                Pair pair = stack.pop();//NOTE EVERY ELEMENT INSIDE THIS LOOP IS CONSIDERED SMALLEST ELEMENT.\n                int start = pair.index;\n                int val = pair.value;\n                long total = prefix[i] - prefix[start];// Total will always contain the sum of that-index\n                res = Math.max(res, val * total);// NOTE: maxSumMinProduct so max is taken care in res = Math.max(res,total*val).But the minimum is taken care in the NSE condition because every element inside this loop body is considered a minimum Element.\n                newStart = start;\n            }\n            \n            if(i<n)stack.push(new Pair(newStart, nums[i]));\n        }\n        \n        return (int)(res % (MOD));\n    }\n    class Pair {\n        int index, value;\n        \n        Pair(int index, int value) {\n            this.index = index;\n            this.value = value;\n        }\n    }\n}\n\n```\n```java []\nclass Solution {\n    \n    private static final int MOD = (int)(1e9+7);\n    \n    public int maxSumMinProduct(int[] nums) {\n        long res = 0;\n        Stack<Pair> stack = new Stack<>();\n        long[] prefix = new long[nums.length + 1];\n        \n        // Compute the prefix sums\n        for (int i = 0; i < nums.length; i++) {\n            prefix[i + 1] = prefix[i] + nums[i];\n        }\n        \n        // Traverse through the nums array\n        for (int i = 0; i < nums.length; i++) {\n            int newStart = i;\n            \n            while (!stack.isEmpty() && stack.peek().value > nums[i]) {\n                Pair pair = stack.pop();\n                int start = pair.index;\n                int val = pair.value;\n                long total = prefix[i] - prefix[start];\n                res = Math.max(res, val * total);\n                newStart = start;\n            }\n            \n            stack.push(new Pair(newStart, nums[i]));\n        }\n        \n        // Process the remaining elements in the stack\n        while (!stack.isEmpty()) {\n            Pair pair = stack.pop();\n            int start = pair.index;\n            int val = pair.value;\n            long total = prefix[nums.length] - prefix[start];\n            res = Math.max(res, val * total);\n        }\n        \n        return (int)(res % (MOD));\n    }\n    class Pair {\n        int index, value;\n        \n        Pair(int index, int value) {\n            this.index = index;\n            this.value = value;\n        }\n    }\n}\n\n```\n\n                        `Hope that clears the doubt`\n## 84. Largest Rectangle in Histogram\n```java []\n//Next Smaller Element to the right pattern \n\n/*for (int i = 0; i < n; i++) {\n            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {\n                ans[stack.pop()] = arr[i]; //Next Smaller Element to the right pattern \n            }\n            stack.push(i);\n}\n\n*/\nimport java.util.Stack;\n\npublic class Solution {\n\n\n    public int largestRectangleArea(int[] heights) {\n        int maxArea = 0;\n        Stack<Pair> stack = new Stack<>();\n\n        for (int i = 0; i < heights.length; i++) {\n            int start = i;\n            // Pop elements from stack while the current height is less than the height at stack\'s top\n            while (!stack.isEmpty() && stack.peek().height > heights[i]) {\n                Pair pair = stack.pop();\n                int index = pair.index;\n                int height = pair.height;\n                int length =i-index;\n                maxArea = Math.max(maxArea, height * length);\n                start = index;  // Update start to the index of the popped element\n            }\n            stack.push(new Pair(start, heights[i]));  // Push current index and height as a pair\n        }\n\n        // Process remaining elements in the stack\n        for (Pair pair : stack) {\n            int index = pair.index;\n            int height = pair.height;\n            maxArea = Math.max(maxArea, height * (heights.length - index));\n        }\n\n        return maxArea;\n    }\n    class Pair {\n        int index;\n        int height;\n\n        Pair(int index, int height) {\n            this.index = index;\n            this.height = height;\n        }\n    }\n}\n\n\n```\n
['Java']