Clean yet still beating them all accepted with 8ms in C++


  • 2
    class Solution {
    private:
        int getMax(int* heights, int* stack, int size)
        {
            int cur = 0, max = 0, top = 0;
            stack[top] = -1;
            for(int i = 0; i < size; ++i)
            {
                while(top>0 && heights[stack[top]]>heights[i])
                {
                    cur = (i-stack[top-1]-1)*heights[stack[top]];
                    top--;
                    if(cur > max) max = cur;
                }
                stack[++top] = i;
            }
            return max;
        }
    public:
        int maximalRectangle(vector<vector<char>>& matrix) 
        {
            int rowSize = matrix.size();
            if(!rowSize) return 0;
            int colSize = matrix[0].size();
            int heights[colSize+1]{0}, stack[colSize+1]{0}, largest = 0;
            for(int r = 0; r < rowSize; ++r)
            {
                for(int c = 0; c < colSize; ++c)
                    matrix[r][c]=='1'? heights[c]++ : heights[c]=0;
                largest = max(largest, getMax(heights, stack, colSize+1));
            }
            return largest;
        }
    };

  • 0
    This post is deleted!

  • 0
    This post is deleted!

  • 1

    Some comments can be helpful


    class Solution {
    private:
        int getLargest(int* heights, int* stack, int size)
        {
            int current = 0, max = 0, top = 0; 
            stack[top] = -1; //ensure the width of the area is okay, hitting the bottom of stack;
            for(int i = 0; i < size; ++i)
            {
                while(top>0 && heights[stack[top]]>heights[i]) //keep the stack in ascending order;
                {
                    current = (i-stack[top-1]-1) * heights[stack[top]]; //get the area started with the height indexes by stack[top];
                    top--;
                    if(current > max) max = current;
                }
                stack[++top] = i;
            }
            return max;
        }
    public:
        int maximalRectangle(vector<vector<char>>& matrix) 
        {
            int rowSize = matrix.size();
            if(rowSize == 0) return 0;
            int colSize = matrix[0].size();
            int heights[colSize+1] = {0}; //spare another column for sentinel so when we finish checking heights, it can automatically collect the leftover in stack;
            int stack[colSize+1] = {0}; //stay ascending order to avoid redundant calculation;
            int largest = 0;
            for(int r = 0; r < rowSize; ++r)
            {
                for(int c = 0; c < colSize; ++c) matrix[r][c]=='1'? heights[c]++ : heights[c]=0;
                largest = max(largest, getLargest(heights, stack, colSize+1));
            }
            return largest;
        }
    };

  • 0
    S

    @LHearen Very impressive solution, clean and efficient. Thank you!


  • -1
    S

    Unbelievable! Beating almost all the others! Great, man!


Log in to reply
 

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