TLE exceeded for TC 1000000000


  • 0
    S

    Please help

    class Solution {
    public:
        int largestRectangleArea(vector<int>& heights) {
            if(heights.size()==0)return 0;
            int max =0;
            for(int i=0;i<heights.size();i++){
                if(heights[i]>max)max= heights[i];
                int count = 1;
                for(int j=i-1;j>=0;j--){
                    if(heights[i]<=heights[j])count++;
                    else break;
                }
                for(int j=i+1;j<heights.size();j++){
                    if(heights[i]<=heights[j])count++;
                    else break;
                }
                int area = count*heights[i];
                if(area>max)max=area;
            }
            return max;
        }
    };
    

  • 0

    @siddharth1 Your solution is quite direct but inefficient indeed that's why you just cannot get passed. Actually we can take advantage of stack here to keep the solution in linear time cost.

    class Solution {
    public:
        int largestRectangleArea(vector<int>& heights) 
        {
            heights.push_back(0);
            int size = heights.size();
            int stack[size]{0}, top = -1;
            stack[++top] = -1;
            int maxArea = 0;
            for(int i = 0; i < size; ++i)
            {
                while(top>0 && heights[stack[top]]>heights[i])
                {
                    maxArea = max(maxArea, (i-stack[top-1]-1)*heights[stack[top]]);
                    top--;
                }
                stack[++top] = i;
            }
            return maxArea;
        }
    };
    

    I've also posted before here. Good luck!


Log in to reply
 

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