[Java] Same as Maximum Rectangle in Histogram | NSL | NSR | Aditya Verma
\nclass Solution {\n    public int maximalRectangle(char[][] matrix) {\n        int m = matrix.length;\n        int n = matrix[0].length;\n        int[] heights
```\nclass Solution {\n    public int maximalRectangle(char[][] matrix) {\n        int m = matrix.length;\n        int n = matrix[0].length;\n        int[] heights = new int[n];\n           \n        int ans = Integer.MIN_VALUE;\n        \n        for(int i=0; i<m; i++) {\n            for(int j=0; j<n; j++) {\n               heights[j] = matrix[i][j] == \'1\' ? heights[j] + 1: 0;\n            }\n            ans = Math.max(ans, getMAH(heights, n));\n        }\n        \n        return ans;\n    }\n    \n    private int getMAH(int[] heights, int n) {\n        int maxArea = Integer.MIN_VALUE;\n        List<Integer> nsl = NSL(heights, n);\n        List<Integer> nsr = NSR(heights, n);\n        int[] width = new int[n];\n        \n        for(int i=0; i<n; i++)\n            width[i] = nsr.get(i) - nsl.get(i) - 1;\n                \n        for(int i=0; i<n; i++) {\n            int area = heights[i] * width[i];\n            maxArea = Math.max(maxArea, area);\n        }\n        return maxArea;\n    }\n    \n    \n    private List<Integer> NSL(int[] heights, int n) {\n            \n        List<Integer> nsl = new ArrayList<>();\n        Stack<int[]> st = new Stack<>();\n        \n        for(int i=0; i<n; i++) {\n            int curr = heights[i];\n            while(!st.isEmpty() && st.peek()[0] >= curr) { st.pop(); }\n            if(st.isEmpty()) nsl.add(-1);\n            else nsl.add(st.peek()[1]);\n            st.add(new int[] { curr, i });\n        }\n        \n        return nsl;\n    }\n    \n    \n     private List<Integer> NSR(int[] heights, int n) {\n            \n        List<Integer> nsr = new ArrayList<>();\n        Stack<int[]> st = new Stack<>();\n        \n        for(int i=n-1; i>=0; i--) {\n            int curr = heights[i];\n            while(!st.isEmpty() && st.peek()[0] >= curr) { st.pop(); }\n            if(st.isEmpty()) nsr.add(n);\n            else nsr.add(st.peek()[1]);\n            st.add(new int[] { curr, i });\n        }\n         \n        Collections.reverse(nsr);\n        return nsr;\n    }\n    \n}\n```
['Stack', 'Java']