[LeetCode]Largest Rectangle in Histogram

1580 단어 LeetCode
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3] .
 
The largest rectangle is shown in the shaded area, which has area = 10 unit.
 
For example, Given height = [2,1,5,6,2,3] , return 10 .
사고: 각 직사각형의 가장 왼쪽과 오른쪽이 자신보다 높은 직사각형을 기록하고 왼쪽과 오른쪽이 서로 줄어들면 길이가 되고 직사각형의 높이를 곱하면 현재 직사각형의 최대 면적을 구성할 수 있다.최대치를 구하다.
struct Node{

	int height;

	int left;

	int right;

	int area;

};

class Solution {

public:

    int largestRectangleArea(vector<int> &height) {

        // IMPORTANT: Please reset any member data you declared, as

        // the same Solution instance will be reused for each test case.

		

		int i;

		int maxarea=0;

		int len=height.size();

		Node *h=new Node[len+2];

		for(i=1;i<=len;i++)

		{

			h[i].height=height[i-1];

			h[i].left=i;

			h[i].right=i;

		}

	

		h[0].height=-1;

		h[len+1].height=-1;

		for(i=1;i<=len;i++)

		{

			while(h[i].height<=h[h[i].left-1].height)

				h[i].left=h[h[i].left-1].left;

		}

	

		for(i=len;i>=1;i--)

		{

			while(h[i].height<=h[h[i].right+1].height)

				h[i].right=h[h[i].right+1].right;

		}

		for(i=1;i<=len;i++)

		{

			h[i].area=h[i].height*(h[i].right-h[i].left+1);

			if(maxarea<h[i].area)

				maxarea=h[i].area;

		}



		delete []h;

		return maxarea;

	}

};


좋은 웹페이지 즐겨찾기