My 8ms C solution with stack.


  • 0
    P
    int largestRectangleArea(int* height, int heightSize) {
        int max = 0;
        int tmp = 0;
        int *s = NULL;
        int h = -1;
        for(int i = 0; i <= heightSize; i++)
        {
            while(h>=0)
            {
                if(i == heightSize || height[s[h]] >= height[i])
                {
                    tmp = height[s[h]]*(i - (h>0?(s[h-1]+1):0));
                    if(tmp > max)
                    {
                        max = tmp;
                    }
                    h--;
                }
                else
                {
                    break;
                }
            }
            s = (int*)realloc(s, sizeof(int)*(h+2));
            s[++h] = i;
        }
        
        return max;
    }

Log in to reply
 

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