## Sunday, December 23, 2012

### [LeetCode] Largest Rectangle in Histogram 解题报告

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`.
» Solve this problem

[解题思路]

[Code]
``````1:  int largestRectangleArea(vector<int> &height) {
2:      // Start typing your C/C++ solution below
3:      // DO NOT write int main() function
4:      //int result[height.size()];
5:      int maxV = 0;
6:      for(int i =0; i< height.size(); i++)
7:      {
8:        int minV = height[i];
9:        for(int j =i; j>=0; j--)
10:        {
11:          minV = std::min(minV, height[j]);
12:          int area = minV*(i-j+1);
13:          if(area > maxV)
14:            maxV = area;
15:        }
16:      }
17:      return maxV;
18:    }
``````

``````1:  int largestRectangleArea(vector<int> &height) {
2:       int maxV = 0;
3:       for(int i =0; i< height.size(); i++)
4:       {
5:            if(i+1 < height.size()
6:                      && height[i] <= height[i+1]) // if not peak node, skip it
7:                 continue;
8:            int minV = height[i];
9:            for(int j =i; j>=0; j--)
10:            {
11:                 minV = std::min(minV, height[j]);
12:                 int area = minV*(i-j+1);
13:                 if(area > maxV)
14:                 maxV = area;
15:            }
16:       }
17:       return maxV;
18:  }
``````

``````1:     int largestRectangleArea(vector<int> &height) {
2:      // Start typing your C/C++ solution below
3:      // DO NOT write int main() function
4:      int stack[height.size()+1], width[height.size()+1];
5:      if(height.size() == 0) return 0;
6:      int top = 0, area = INT_MIN;
7:      stack[0] = 0;
8:      width[0] = 0;
9:      int newHeight;
10:     for(int i =0; i<= height.size(); i++)
11:     {
12:        if(i < height.size()) newHeight = height[i];
13:        else newHeight = -1;
14:        if(newHeight>= stack[top])
15:        {
16:            stack[++top] = newHeight;
17:            width[top] = 1;
18:        }
19:        else
20:        {
21:            int minV = INT_MAX;
22:            int wid= 0;
23:            while(stack[top] > newHeight)
24:            {
25:               minV = min(minV, stack[top]);
26:               wid += width[top];
27:               area = max(area, minV*(wid));
28:               top--;
29:             }
30:             stack[++top] = newHeight;
31:             width[top] = wid+1;
32:         }
33:      }
34:      return area;
35:    }
``````

[总结]

Update: Refactor code 5/7/2013

``````1:  int largestRectangleArea(vector<int> &h) {
2:       stack<int> S;
3:       h.push_back(0);
4:       int sum = 0;
5:       for (int i = 0; i < h.size(); i++) {
6:            if (S.empty() || h[i] > h[S.top()]) S.push(i);
7:            else {
8:                 int tmp = S.top();
9:                 S.pop();
10:                 sum = max(sum, h[tmp]*(S.empty()? i : i-S.top()-1));
11:                 i--;
12:            }
13:       }
14:       return sum;
15:  }
``````