Sharing my C# Solution


  • 0

    Similar solutions have been shared many times but here's mine. It uses the solution for Largest Rectangle under histogram.

    public class Solution {
        public int LargestRectangleArea(int[] heights) {
            var stack = new Stack<int>();
            int maxArea = 0;
                
            for(int i=0; i < heights.Length; i++) {
                if(stack.Count==0 || heights[i] > heights[stack.Peek()]) {
                    //increasing height - push to stack
                    stack.Push(i);
                } else {
                    //encountered smaller bar - compute area where this bar is the rightmost bar
                    while(stack.Count > 0 && heights[stack.Peek()] >= heights[i]) {
                        //remove bars greater than rightmost bar
                        int height = heights[stack.Pop()];
                        int left = stack.Count > 0 ? stack.Peek() : -1;
                        maxArea = Math.Max(maxArea, (i-left-1)*height);
                    }
                    stack.Push(i);
                }
            }
                
            //process remaining bars on stack
            while(stack.Count !=0) {
                int height = heights[stack.Pop()];
                int left = stack.Count > 0 ? stack.Peek() : -1;
                maxArea = Math.Max(maxArea, (heights.Length-left-1)*height);
            }
                
            return maxArea;
        }
            
        public int MaximalRectangle(char[,] matrix) {
            int[,] mm = new int[matrix.GetLength(0),matrix.GetLength(1)];
            
            //create vertical "histogram bars"
            for(int c=0; c < matrix.GetLength(1); c++) 
            for(int r=0; r < matrix.GetLength(0); r++) {
                if(matrix[r,c]=='1') {
                    mm[r,c] = (r-1 >= 0 ? mm[r-1,c] : 0) + 1;    
                }
            }
            
            int maxRect = 0;
            int[] hist = new int[mm.GetLength(1)];
            for(int r=0; r < mm.GetLength(0); r++) {
                for(int i=0; i < hist.Length; i++) hist[i] = mm[r,i];
                maxRect = Math.Max(maxRect, LargestRectangleArea(hist));    
            }
            
            return maxRect;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.