一、題目要求
給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度，并且每個柱子彼此相鄰，且寬度為 1 ，求在該柱狀圖中，能夠勾勒出來的矩形的最大面積，
- 以下是柱狀圖的示例，其中每個柱子的寬度為 1，給定的高度為 [2,1,5,6,2,3]，
- 圖中陰影部分為所能勾勒出的最大矩形面積，其面積為 10 個單位，如下：
- 示例：
輸入: [2,1,5,6,2,3]
輸出: 10
二、示例演算法
- 解題思路
- 為什么要找左右兩邊高度大于當前遍歷的高度的下標？因為只有高度大于當前高度，面積才有可能更大，如果找<=的，面積只可能小于或者等于原先計算的最大面積，
- 為什么單調增堆疊要存盤下標，而不是高度？因為通過下標可以找高度，而且通過下標是唯一的，這樣才能找到對應位置的對應高度，
- 進入外層回圈，向右延伸，是確定了高度大于當前高度的最右下標，
- 進入內層回圈，由于單調增堆疊的特性，堆疊pop出來的的一定是高度大于當前高度的最左下標，
- area =（（外層回圈的下標-1）-（內層回圈走到的下標））* 內層回圈pop出來的高度，然后取最大值，
- 陣列頭尾加入0，當作哨兵，所以一定會找到比當前index的高度還小的值，結束左右尋找的流程，
- 暴力解法（Swift），O(n2) 會超出時間限制：
func largestRectangleArea(_ heights: [Int]) -> Int {
if heights.count == 0 { return 0 }
var maxArea: Int = 0
for (index, height) in heights.enumerated() {
if height <= 0 { continue }
var curMax: Int = height
// 向左延伸，找到高度大于等于當前index的最小下標
for leftIndex in (0..<index).reversed() {
if heights[leftIndex] >= height {
curMax = curMax + height
} else {
break
}
}
// 向右延伸，找到高度大于等于當前index的最大下標
if index < heights.count-1 {
for rightIndex in (index+1)..<heights.count {
if heights[rightIndex] >= height {
curMax = curMax + height
} else {
break
}
}
}
maxArea = max(curMax, maxArea)
}
return maxArea
}
- 單調增堆疊（Swift）
func largestRectangleArea(_ heights: [Int]) -> Int {
var heights = [0] + heights + [0]
var maxArea: Int = 0
var stack: [Int] = []
for (index, height) in heights.enumerated() {
while !stack.isEmpty && stack.last != nil && heights[stack.last!] > height {
let removed = stack.removeLast()
if let leftEdge = stack.last {
var rightEdge = index
maxArea = max(maxArea, heights[removed] * (rightEdge - 1 - leftEdge))
}
}
stack.append(index)
}
return maxArea
}
- C 單調堆疊的演算法實作
typedef struct {
void **data;
int top;
int size;
} Stack;
Stack *StackCreate(int stackSize) {
Stack *stack = (Stack *)malloc(sizeof(Stack));
if (stack == NULL) {
return NULL;
}
stack->data = (void **)malloc(sizeof(void **) * (stackSize + 1));
memset(stack->data, 0, sizeof(void **) * (stackSize + 1));
stack->top = -1;
stack->size = stackSize;
return stack;
}
void StackFree(Stack *obj) {
if (obj->data != NULL) {
free(obj->data);
obj->data = NULL;
}
free(obj);
obj = NULL;
return;
}
bool IsStackEmpty(Stack *obj) {
return (obj->top == -1);
}
bool IsStackFull(Stack *obj) {
return (obj->top == obj->size);
}
// 泛型介面，使用void *
void StackPush(Stack *obj, void *data) {
if (IsStackFull(obj) == true) {
return;
}
int top = obj->top;
obj->data[++top] = data;
obj->top = top;
return;
}
void StackPop(Stack *obj) {
if (IsStackEmpty(obj) == true) {
return;
}
void *data = obj->data[obj->top];
if (data != NULL) {
free(data);
data = NULL;
}
obj->top--;
return;
}
void *StackTop(Stack *obj) {
if (IsStackEmpty(obj) == true) {
return NULL;
}
return (obj->data[obj->top]);
}
void StackClear(Stack *obj) {
if (IsStackEmpty(obj) == true) {
return;
}
for (int i = 0; i <= obj->top; i++) {
void *data = obj->data[i];
if (data != NULL) {
free(data);
data = NULL;
}
}
obj->top = -1;
return;
}
void StackPushInt(Stack *obj, int value) {
int *node = (int *)malloc(sizeof(int));
*node = value;
StackPush(obj, node);
return;
}
int StackTopInt(Stack *obj) {
if (IsStackEmpty(obj) == true) {
return -1;
}
return *(int *)(obj->data[obj->top]);
}
void StackPushStr(Stack *obj, char *str, int strSize) {
char *node = (char *)malloc(sizeof(char) * (strSize + 1));
memcpy(node, str, strSize);
node[strSize] = '\0';
StackPush(obj, node);
return;
}
char *StackTopStr(Stack *obj) {
if (IsStackEmpty(obj) == true) {
return NULL;
}
return (char *)(obj->data[obj->top]);
}
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int largestRectangleArea(int* heights, int heightsSize) {
int *data = (int *)malloc(sizeof(int) * (heightsSize + 1));
memcpy(data, heights, sizeof(int) * heightsSize);
data[heightsSize] = 0;
Stack *monotoneStack = StackCreate(heightsSize + 1);
int ret = 0;
for (int i = 0; i <= heightsSize; i++) {
int top = StackTopInt(monotoneStack);
while ((IsStackEmpty(monotoneStack) != true) && (data[top] >= data[i])) {
int h = data[top];
StackPop(monotoneStack);
top = StackTopInt(monotoneStack);
int sidx = top;
ret = MAX(ret, (h * (i - sidx - 1)));
}
StackPushInt(monotoneStack, i);
}
StackFree(monotoneStack);
return ret;
}
三、單調堆疊的理解（C++為例）
① 定義
- 定義：堆疊內元素保持有序的狀態的堆疊稱為單調堆疊，如下圖所示：
- 單調堆疊是一個定義簡單但應用起來比較復雜的資料結構，其根本應用可以概括為：在一個一維陣列中，幫助我們找到某個元素的左側或右側第一個大于或小于該元素的數，
- 具體來說，我們會維護一個單調堆疊（遞增或遞減視要求而定），這個堆疊在滿足一定情況時會將堆疊頂元素出堆疊(pop)，一旦這種情況發生，那么一定是遇到了我們要找的大于（或小于）該堆疊頂元素的數，相應的，我們應該在此時進行一系列的操作，得到我們想要的結果，核心在于如何正確理解出堆疊的含義，
② 佇列中數帽子問題
- 現有一條排好的隊伍，從隊首到隊尾，隊員們都戴著帽子，身高是無序的，假設每個人能看到隊伍中在他前面的比他個子矮的人的帽子，（如果出現一個比這個人個子高的人擋住視線，那么此人不能看到高個子前面的任何人的帽子）現在請計算出這個隊伍中一共可以看到多少個帽子？例如給定陣列為：[2,1,5,6,2,3]（順序為從隊尾到隊首），如下所示：
- 分析上圖可以得出，答案為3，從暴力角度嘗試去解這道題，顯然可以做到，對于陣列中每個元素，向右去找所有比它小的元素（找第第一個比它大的元素），這樣總的時間復雜度為O(n^2)，最壞情況是這是一個單調遞減陣列，每次都要向右找到陣列的最末尾，顯然這不是理想的解法，我們可以應用單調堆疊來解決這個問題，其代碼如下：
int countHats(vector<int>& heights) {
heights.push_back(INT_MAX);
stack<int> stk;
int sum = 0;
for(int i=0; i<heights.size(); i++) {
while( !stk.empty() && heights[i] > heights[stk.top()]) ) {
int top = stk.top();
stk.pop();
sum += i – top – 1;
}
stk.push(i);
}
return sum;
}
- 分析以上代碼：
- 在以上代碼中，我們維護了一個單調遞減堆疊，在堆疊中的元素都是單調遞減的，這表明堆疊內的元素還可能看到比它更小的元素（帽子），
- 當遇到一個比堆疊頂元素大的元素時，說明堆疊頂元素不可能看到比它更小的元素了（因為遮擋作用），這時將堆疊頂元素pop出來，同時更新sum的值，sum += i – top – 1，表示堆疊頂元素與這個新元素間的距離，也就是堆疊頂元素能看到的最多的帽子數，
- 在for回圈中，每個元素都會入堆疊和出堆疊，在出堆疊程序中總會計算出堆疊頂元素能看到的最多的帽子數，并更新sum值，當整個佇列回圈結束后，得到的sum值就是最后隊伍中能看到的帽子總數，
- 注意為了使所有元素都能出堆疊（糟糕情況是單調遞減數列，這時似乎一次出堆疊都沒有發生，原因是最后一個元素后面不可能有新的元素出現了，但單調堆疊還在期待新的元素出現，為了反映元素不再出現這一事實，我們假設最后一個元素后面出現了一個無窮大的元素），即heights.push_back(INT_MAX)，
③ 尋找第一個比自己大的數
- 給一個陣列，回傳一個大小相同的陣列，回傳的陣列的第i個位置的值應當是，對于原陣列中的第i個元素，至少往右走多少步，才能遇到一個比自己大的元素（如果之后沒有比自己大的元素，或者已經是最后一個元素，則在回傳陣列的對應位置放上-1），
- 例如給定陣列為：[2,1,5,6,2,3]，回傳陣列應該為：[2,1,1,-1,1,-1]，
- 其實這個問題本質上和數帽子問題是一樣的，本質都是找到元素右邊第一個比它大的數，代碼稍作改動即可，
int countSteps(vector<int>& heights) {
stack<int> stk;
vector<int> results(heights.size(), -1);
for(int i=0; i<heights.size(); i++) {
while( !stk.empty() && heights[i] > heights[stk.top()]) ) {
results[stk.top()] = i – stk.top();
stk.pop();
}
stk.push(i);
}
return results;
}
④ 最大矩形面積問題
- 給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度，每個柱子彼此相鄰，且寬度為 1 ，求在該柱狀圖中，能夠勾勒出來的矩形的最大面積，
- 如上圖，矩形最大面積為10，這個問題同樣可以借助單調堆疊來解決，在這之前，需要理解如何找到這個最大面積矩形，這個矩形的限制條件有兩個，一個是高度（也即組成矩形的最短的那根柱子高度），一個是寬度，（也即組成矩形的柱子個數），
- 為了找到這個全域最大值，我們遍歷所有區域最優情況，那么什么是區域最優解呢？我們將每個柱子的高度作為包含它的矩形的高度，也即這個柱子一定是這個矩形中最低的一個柱子，那么我們下一步是求解這個矩形的寬度，顯然我們只需找到這個柱子左邊，右邊第一個比它低的柱子，就可以求出寬度，這顯然讓我們想到使用單調堆疊的資料結構，代碼如下：
int largestRectangleArea(vector<int> heights) {
int maxArea = 0;
heights.push_back(0);
// monotone stack(ascending)
stack<int> stk;
for(int i = 0; i < heights.size(); i++) {
while(!stk.empty() && heights[i] < heights[stk.top()]) {
int top = stk.top();
// find the smaller element to the left of the current element
stk.pop();
maxArea = max(maxArea,heights[top]*(stk.empty() ? i : (i - stk.top()-1)));
}
stk.push(i);
}
return maxArea;
}
- 我們維護一個單調遞增堆疊，當遇到一個新元素小于堆疊頂元素時，發生出堆疊行為，表示堆疊頂元素向右遇到了第一個小于它的元素，同時在堆疊內的堆疊頂元素的下面一個元素即是堆疊頂元素向左尋找時第一個小于它的元素（這一點的原因值得仔細思考，其實是因為堆疊頂元素與其下面的元素間在原陣列中或許存在很多的元素，但它們必然是比堆疊頂元素大且比堆疊頂元素下面的元素小的，它們都在之前被彈出了堆疊），
- 在出堆疊行為發生后，我們需要計算以堆疊頂元素的高度值作為矩形高度時的矩形面積，而矩形寬度已經可以計算了，因為我們找到了堆疊頂元素左右兩側小于它的第一個元素，于是區域最優解得到計算，在整個回圈中，所有元素進堆疊一次，出堆疊一次，時間復雜度為O(n)，
- 我們考慮本題中的第4號柱子作為堆疊頂元素時會發生的情況：
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/158804.html
標籤：其他