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
.
方法1:
这个方法会TLE!
O(n log n),而且最快情况下,变成O(n^2).
之所以把这个写下来,是因为我蠢!
对于任意i~j, area = (j-i+1) * min(a[i]...a[j]);
因此在i~j内,如果要有更大的area,则必定需要去掉a[k] = min(a[i]...a[j]).
去掉a[k]后,则分成2段:i~k-1, k+1~j。则变成2个子问题。
class Solution { public: int largestRectangleArea(vector<int> &height) { if (height.size() == 0) return 0; return maxarea(&height[0], 0, height.size() - 1); } int maxarea(int* a, int start, int end) { if (start > end) return 0; if (start == end) return a[start]; int minidx = start, minh = a[minidx]; for (int i = start+1; i <= end; i++) { if (a[i] < minh) { minh = a[i]; minidx = i; } } int tmp = (end - start + 1) * minh; int left = maxarea(a, start, minidx - 1); int right = maxarea(a, minidx + 1, end); int res = max(tmp, left); res = max(res, right); return res; } };
方法2:
对于每一块板,找到left,right两边。离它最远的那个比不它矮的板。也就是等价于找到离他最近的那个比它矮的板a[k]。那么a[k-1]那块就是最远的不比他短的板。因为找到离他最近的比他矮的板,这是一个单调序列问题,可以O(N)处理。
所以分别O(N)处理left,right。
然后再O(N)扫一遍,对于每快以a[i]为最矮的矩形面积为maxarea[i] = (right-left) * a[i];
class Solution { public: int largestRectangleArea(vector<int> &height) { int len = height.size(); if (len == 0) return 0; vector<int> left(len, -1); vector<int> right(len, -1); left[0] = -1; stack<int> s; int *a = &height[0]; for (int i = 0; i < len; i++) { while (!s.empty()) { if (a[s.top()] >= a[i]) s.pop(); else break; } if (!s.empty()) left[i] = s.top(); else left[i] = -1; s.push(i); } while(!s.empty()) s.pop(); for (int i = len - 1; i >= 0; i--) { while (!s.empty()) { if (a[s.top()] >= a[i]) s.pop(); else break; } if (!s.empty()) right[i] = s.top(); else right[i] = len; s.push(i); } int res = -1; for (int i = 0; i < len; i++) { res = max(res, height[i]*(right[i] - left[i] - 1)); } return res; } };