0084 柱状图中最大的矩形

困难单调栈

算法思路

初见此题，我第一反应是动态规划。动态规划用于解决重复子问题，根据题目描述，很容易想到：如果说当前有编号第 0 ~ heightsSize-1 个柱子，它们组成的最大矩形是由第 a ~ b 个柱子组成的。那么，对于编号 [0,a] ~ [b,heightsSize-1] 个柱子，它们形成的最大矩形的面积是相同的。而这些问题的解是相同的，可以使用动态规划避免重复子问题。

由上述分析，我总结如下状态转移方程：

\[ \displaystyle maxSize[l][r] = \max \left \{ \begin{array}{cc} maxSize[l+1][r] \\ maxSize[l][r-1] \\ min[l][r] * (r-l+1) \end{array} \right. \]

并形成如下代码：

int largestRectangleArea(int* heights, int heightsSize) {
    int sum[heightsSize][heightsSize] = {};
    int min[heightsSize][heightsSize] = {};
    for (int i = 0; i < heightsSize; i++) {
        sum[i][i] = heights[i];
        min[i][i] = heights[i];
    }
    for (int len = 1; len < heightsSize; len++) {
        for (int left = 0; left < heightsSize - len; left++) {
            if (heights[left + len] < min[left][left + len - 1]) {
                min[left][left + len] = heights[left + len];
            } else {
                min[left][left + len] = min[left][left + len - 1];
            }
            sum[left][left + len] =
                max(sum[left][left + len - 1], sum[left + 1][left + len],
                    min[left][left + len] * (len + 1));
        }
    }
    return sum[0][heightsSize - 1];
}

然而提交评测后发现仅能通过部分测试点。对代码分析后不难发现，使用动态规划算法的时间复杂度为 \(O(n^2)\)，空间复杂度为 \(O(n^2)\)。而本题的数据范围有 1 <= heightsSize <= 10^5，\(n^2\) 级别的复杂度是不能接受的。

阅读题解后，才理解了新的思路：观察题目不难证明，对于每一个“最大矩形”，它的高一定是其宽度范围内某个柱形的高度。因此，我们抛弃刚才的 “通过首尾柱形”寻找最大矩形，而是“针对每个柱子”寻找以这个柱子为高，且包含这个柱子的最大矩形。

然而，如果暴力求解：对于每个柱子都向左（右）遍历找到比它矮的柱子，并计算对应矩形大小。尽管空间复杂度不高，但时间复杂度依旧 \(O(n^2)\)，不符合预期。

但是，有一点值得注意：不论如何我们都要对每一个柱子进行一次遍历。那么应当设计一个算法，在一次遍历中找到每个柱子左右两侧矮于它的柱子。

联想：中缀表达式转后缀表达式。在这个经典问题中，我们需要根据运算符优先级输出，优先级高的先输出。换言之，在一次遍历中，通过弹栈入栈的方法，即可确定整个表达式的运算顺序。如果将每个运算符（括号不算）视作一个柱子，优先级为柱子高度，即可发现两者相似之处。

因此，本题的方法即为单调栈。按顺序遍历每一个柱子，当柱子高度大于当前栈顶的柱子时，将当前柱子入栈。当柱子高度小于栈顶柱子时，相当于我们找到了栈顶柱子右侧第一个比它低的柱子。此时弹栈计算矩形面积直至柱子高度大于当前栈顶柱子。而单调栈的核心在于：栈中每个元素的前一个元素，即是这个柱子左侧第一个比它低的柱子。

代码实现

largest-rectangle-in-histogram.c

#define max(a, b) ((b) > (a) ? (b) : (a))

int largestRectangleArea(int* heights, int heightsSize) {
    int* stack = malloc((heightsSize + 5) * sizeof(int));
    int maxSize = 0;
    int index = 0;
    stack[0] = -1;
    for (int i = 0; i <= heightsSize; i++) {
        int h = i < heightsSize ? heights[i] : 0;
        while (stack[index] >= 0 && h < heights[stack[index]]) {
            int high = heights[stack[index]];
            maxSize = max(maxSize, high * (i - stack[index - 1] - 1));
            index--;
        }
        stack[++index] = i;
    }
    return maxSize;
}

观察代码的小巧思：我们对首尾各增加一个高度为 0 的柱子，方便入栈弹栈。