Leetcode.84.Largest Rectangle in
2019-10-16 本文已影响0人
Jimmy木
题目
给定一个数组, 数组构成一个柱状图, 柱状图每个柱状高度为数组值, 宽度为1. 求柱状图中最大的矩形面积.
Input: [2,1,5,6,2,3]
Output: 10
思路1
循环嵌套, 简单粗暴.
时间复杂度O(n²)
int largestRectangleArea(vector<int>& heights) {
int n = (int)heights.size();
int res = 0;
for (int i = 0;i < heights.size();i++) {
int minRec = heights[i];
int minHeight = heights[i];
for (int j = i-1;j >= 0 ;j--) {
int width = i - j + 1;
minHeight = min(minHeight, heights[j]);
if (minHeight * width > minRec) {
minRec = minHeight * width;
}
}
res = max(res, minRec);
}
return res;
}
思路2
针对每个柱状图, 向左右寻找不比自己小的柱状.
时间复杂度O(n²/2)
int largestRectangleArea(vector<int>& heights) {
int n = (int)heights.size();
int res = 0;
for (int i = 0; i < n; i++) {
int h = heights[i];
int l = i, r = i;
while (l >= 0 && h <= heights[l]) l--;
while (r < n && h <= heights[r]) r++;
res = max(res, h * (r - l - 1));
}
return res;
}
思路3
使用栈, 当遇到比自己小的数就出栈, 遇到比自己大的数就入栈.
int largestRectangleArea(vector<int>& a) {
int n = (int)a.size();
int i = 0, maxarea = 0;
stack<int> s;
while(i<n) {
if(s.empty()|| a[s.top()] <= a[i]) {
s.push(i++);
} else {
int t = s.top();
s.pop();
int area = a[t] * (s.empty() ? i : i-s.top()-1);
maxarea = max(maxarea,area);
}
}
while(!s.empty()) {
int t = s.top();
cout << "t : " << t << endl;
s.pop();
int area = a[t] * (s.empty() ? i : i-s.top()-1);
maxarea = max(maxarea,area);
}
return maxarea;
}
总结
从不同角度思考, 灵活运用各种数据结构.