题目分析

这个问题要求在一个由非负整数组成的数组表示的柱状图中找到能够勾勒出来的最大矩形的面积。数组中的每个整数表示柱状图中每个柱子的高度，数组中每个元素的宽度都为1。

解决“柱状图中最大的矩形”问题的关键技术是使用单调栈。

解题思路

解法的核心思路是使用单调栈来解决“柱状图中最大的矩形”问题。

通过维持一个单调递增的栈，我们可以快速找到每个柱子左右两侧第一个高度小于该柱子的位置，从而计算以该柱子为高的最大矩形面积。

Java解法

下面是使用Java语言的解法：

import java.util.Deque;
import java.util.ArrayDeque;

public class Solution {
    public int largestRectangleArea(int[] heights) {
        // 首先在原始高度数组的基础上扩展，前后各添加一个高度为0的柱子
        int len = heights.length;
        int[] extendedHeights = new int[len + 2];
        extendedHeights[0] = 0; // 前端添加高度为0的柱子
        System.arraycopy(heights, 0, extendedHeights, 1, len);
        extendedHeights[len + 1] = 0; // 后端添加高度为0的柱子
        len += 2; // 更新数组长度
        
        // 使用Deque作为单调栈
        Deque<Integer> stack = new ArrayDeque<>();
        stack.addLast(0); // 添加扩展数组的第一个元素索引
        
        int maxArea = 0;
        for (int i = 1; i < len; i++) {
            // 当前柱子的高度小于栈顶柱子的高度时，计算面积
            while (extendedHeights[i] < extendedHeights[stack.peekLast()]) {
                int height = extendedHeights[stack.pollLast()];
                int width = i - stack.peekLast() - 1; // 计算宽度
                maxArea = Math.max(maxArea, height * width);
            }
          	// 当前柱子更大，继续放入栈中，保持单调递增
            stack.addLast(i); // 当前柱子索引入栈
        }
        return maxArea;
    }
}

扩展高度数组：在原始高度数组的前后各添加一个高度为0的柱子。这样做的目的是为了处理边界情况，确保所有柱子都能被考虑到，包括原数组的第一个和最后一个柱子。
使用ArrayDeque作为单调栈：初始化时，将扩展后数组的第一个元素索引（即0，对应高度为0的柱子）加入栈中。这保证了栈不会空，简化了后续逻辑。
计算最大面积：遍历每个柱子，使用单调栈找到每个柱子左右两侧第一个低于其高度的柱子。当遇到使栈顶元素出栈的情况时，即当前柱子的高度小于栈顶柱子的高度，计算由栈顶柱子形成的最大矩形面积，并更新最大面积。
宽度计算：宽度由当前索引i减去新的栈顶索引再减一计算得出，这是因为当前柱子是右边第一个低于栈顶柱子的柱子，而新的栈顶柱子是左边第一个低于原栈顶柱子的柱子。

时间复杂度

O(n)，其中n是输入数组的长度。尽管每个元素都要入栈一次，但由于每个元素最多被弹出栈一次，整个算法的总操作次数保持在2n以内，因此是线性时间复杂度。

空间复杂度

O(n)，主要空间开销来自于单调栈的使用。在最坏的情况下，如果输入数组是单调递增的，那么所有元素都会被推入栈中。

References

84. 柱状图中最大的矩形 ↩︎

趣味算法题

单调栈：柱状图中最大的矩形