【題目敘述】https://leetcode.com/problems/largest-rectangle-in-histogram/
【解題想法】單調棧、分治法
目錄
【做法1】單調棧
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int m = heights.size();
if (m == 0) return 0;
int a[m+2] = {};
int ans = 0;
stack <int> stk;
stk.push(0);
for (int i = 0; i < m; i++){
a[i+1] = heights[i];
}
a[0] = -1;
a[m+1] = -1;
int l[m+2] = {}, r[m+2] = {};
for (int j = 1; j <= m+1; j++){
while(a[stk.top()] > a[j]){
r[stk.top()] = j;
stk.pop();
}
stk.push(j);
}
for (int j = m; j >= 0; j--){
while(a[stk.top()] > a[j]){
l[stk.top()] = j;
stk.pop();
}
stk.push(j);
}
for (int j = 1; j <= m; j++){
ans = max(ans, a[j]*(r[j]-l[j]-1));
}
return ans;
}
};
【做法2】分治法
class Solution {
public:
int dc(vector<int>& heights, int s, int t) {
//D&C, O(NlongN)
if (s >= t) return 0;
if (s+1 == t) return heights[s];
//從中點分成左右兩半,考慮最大矩形落在其中一半
int m = (s + t) / 2;
int max_rect = max(dc(heights, s, m), dc(heights, m+1, t));
//找出跨越中點的最大矩形面積,區間為[i+1, j-1]
int i = m, j = m, h = heights[m], largest = 0;
while (i >= s && j <= t) {
//延伸左右範圍,逐步下降高度
//考慮邊界條件
if (i < s) h = heights[j];
else if (j >= t) h = heights[i];
else h = max(heights[i], heights[j]);
while (i >= s && heights[i] >= h) {
i--;
}
while (j < t && heights[j] >= h) {
j++;
}
largest = max(largest, (j - i - 1) * h);
}
return max(max_rect, largest);
}
int largestRectangleArea(vector<int>& heights) {
return dc(heights, 0, (int)heights.size());
}
};