A C++ solution used conception of stack


  • 0

    The conception of solution is:
    Keep an increase height stack. If stack is empty or current height value is greater than than back value of stack, push the height into stack; if back value of stack is greater or equal to current height, pop out the the values in stack until the back value of stack is less than current height or stack is empty, then push the height into stack.
    The rectangle area of each height consists of two parts - 'left' and 'right'. It is calculated when value in stack popped out.

    int largestRectangleArea(vector<int>& he) 
    {
    	vector<int> inc; //increase height stack
    	int max = 0;
    	he.push_back(0); //in order to make the code concise
    	int sz = he.size();
    	for (int i = 0; i < sz; ++i)
    	{
    		while (!inc.empty() && he[inc.back()] >= he[i])
    		{
    			int t = inc.back();
    			inc.pop_back();
    			int right = he[t] * (i - t);
    			int left = 0;
    			if (!inc.empty())
    				left = he[t] * (t - inc.back() - 1);
    			else if (t > 0)
    				left = he[t] * t;
    			max = left + right > max ? left + right : max;
    		}
    		inc.push_back(i);
    	}
    	return max;
    }
    

Log in to reply
 

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