【数据结构与算法】之柱状图中最大矩形的算法

一、题目要求

给定 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(n²) 会超出时间限制： 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²)，最坏情况是这是一个单调递减数组，每次都要向右找到数组的最末尾。显然这不是理想的解法，我们可以应用单调栈来解决这个问题。其代码如下： 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号柱子作为栈顶元素时会发生的情况：