Largest Rectangle in Histogram
給定n個非負整數表示直方圖的條高,其中每個條的寬度為1,求直方圖中最大矩形的面積。
Python
使用單調棧 :
- 構建一個棧,如果當前元素比棧頂元素高,那麼將該元素入棧
否則,依次從棧頂開始彈出元素,直到找到比當前元素小的元素,這個時候棧頂元素為形成rectangle的左邊界,當前所在位置為右邊界,這樣就可以算出當前rectangle面積 - 這樣就可以通過從前向後遍歷一遍heights就可以得到所有minarea,並從中挑出最大值
- 值得注意的有兩點:1. 棧中保存的元素為heights中相應height的index,這樣才可以一直能夠計算相應的面積2. 需要在heights後加入一個比所有height都小的值,否則的話,包括最後一個height在內的矩形面積便會被忽略
class Solution(object):
def largestRectangleArea(self, heights):
stack = []
maxarea = 0
heights.append(0)
n = len(heights)
for i in range(n):
if not stack or heights[i]>heights[stack[-1]]:
stack.append(i)
else:
while stack and heights[i]<=heights[stack[-1]]:
h = heights[stack[-1]]
stack.pop()
w = i if not stack else i-stack[-1]-1
maxarea = max(maxarea,h*w)
stack.append(i)
return maxarea
C++
方法一
首先找出當前區間中高度最小的柱子,然後分別對它左邊和右邊的區間遞歸求解,並取最大值。最後,我們還需要考慮包含最小柱子的矩形面積,這可以通過最小柱子的高度乘以區間長度來計算。
時間複雜度為 O(n log n),空間複雜度為 O(log n)
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
return helper(heights, 0, heights.size() - 1);
}
private:
int helper(vector<int>& heights, int left, int right) {
if (left > right) {
return 0;
}
int min_index = left;
for (int i = left + 1; i <= right; i++) {
if (heights[i] < heights[min_index]) {
min_index = i;
}
}
return max(heights[min_index] * (right - left + 1),
max(helper(heights, left, min_index - 1),
helper(heights, min_index + 1, right)));
}
};
方法一
對於每個柱子,我們不斷彈出比它高的柱子,計算它們向左和向右最多能延伸多少個柱子,從而得到它們所在的矩形面積。在計算完所有矩形面積後,取最大值即可。為了方便計算,我們在高度數組末尾添加一個高度為 0 的虛擬柱子。
時間複雜度為 O(n),空間複雜度為 O(n)
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
heights.push_back(0);
int n = heights.size();
stack<int> s;
int ans = 0;
for (int i = 0; i < n; i++) {
while (!s.empty() && heights[s.top()] > heights[i]) {
int h = heights[s.top()];
s.pop();
int w = s.empty() ? i : i - s.top() - 1;
ans = max(ans, h * w);
}
s.push(i);
}
return ans;
}
};