EX:
想法:
一開始只能很直覺的想到暴力法，就是對於每個 bar i 分別往左、往右遍歷找到左邊/右邊最後一個不小於他的 bar 的 index (left/right)，然後計算 (right - left + 1)*heights[i]) 之後就可以得到該 bar 所能組成的最大面積矩形，但這個方法的時間複雜度是 O(n^2)，最後一個大測資會吃TLE。
看了一下發現這題大家都用 "Monotonic Stack" 的方式解，可以達到 O(n) time, O(n) space 的複雜度，但我是覺得不大容易自己想到，就紀錄一下。
首先 stack 中要保持遞增順序，因此若 stack 為空或是當前高度 heights[i] 大於等於 stack 的 top 的高度則直接push 進 stack，因為若 heights[i] >= heights[stack.top] 表示前面的 bar 寬度可以延伸到 i 形成更大的矩形，因此還有繼續形成更大矩形的可能所以先不計算，而若 heights[i] < heights[stack.top] 則表示前面的 bar 沒辦法延伸到 i ，因此它所能形成的最大矩形到目前為止已經確定了，可以進行計算，換言之，遇到高度比目前 stack.top 小的 bar 其實是一個開關，遇到這種情況表示 stack.top 的 bar 的右邊界已經找到了就是他自己，所以就可以開始從 stack.top pop stack 中的 bar 出來做計算，一直 pop 到 bar 的高小於 heights[i] 為止 (跟前面一樣，因為高小於當前 bar 的高表示之後還有機會形成更大的矩形)，由於 stack 是遞增的且右邊界確定了，因此 stack 每個 bar 可以形成的矩形大小會是本身個高乘上與邊界的距離(寬)，
i.e. heights[stack.top] * (i - stack.top - 1)。
完整程式碼:
解法一 ( brute-force):
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int max_area = 0;
for (int i = 0; i < heights.size(); i++) {
int left = i;
int right = i;
for (int j = i - 1; j >= 0; j--) {
if (heights[j] >= heights[i]) {
left = j;
}
else {
break;
}
}
for (int j = i + 1; j < heights.size(); j++) {
if (heights[j] >= heights[i]) {
right = j;
}
else {
break;
}
}
max_area = max(max_area, (right - left + 1)*heights[i]);
}
return max_area;
}
};
解法二 (Monotonic stack):
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
vector<int> stack;
// avoid heights is in increasing order
heights.push_back(0);
int i = 0;
int res = 0;
while ( i < heights.size()) {
if (stack.empty() || heights[i] >= heights[stack.back()]) {
stack.push_back(i++);
}
else {
int h = heights[stack.back()];
stack.pop_back();
int w = (stack.empty())? i : i - stack.back() - 1;
res = max(res, h*w);
}
}
return res;
}
};
沒有留言:
張貼留言