1、暴力法

两重循环，找到每个区间最小的柱子高度，乘以区间宽度即可。假设有n个柱子，那么就有n^2个方案，所以时间复杂度是$O(n^2)$的，该方法不能AC。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int maxArea = 0;

        for (int i = 0; i < heights.size(); ++ i)
        {
            int min_val = heights[i];                   //min_val保存区间最矮的柱子高度
            for (int j = i; j < heights.size(); ++ j)
            {
                min_val = min(min_val, heights[j]);
                int area = min_val * (j - i + 1);
                maxArea = max(maxArea, area);           //更新最大面积
            }
        }

        return maxArea;
    }
};

2、分治法

先找到直方图中最矮柱子的下标，这个直方图的最大矩形有三种可能：

1. 矩形通过这根最矮的柱子，它的高度就是最矮的柱子，长度就是起始柱子到终止柱子；
2. 矩形在最矮柱子左侧；
3. 矩形在最矮柱子右侧。

用递归的方式解决问题，时间复杂度为$O(nlogn)$，空间复杂度为$O(logn)$，若直方图中柱子的高度是排序的，则时间复杂度会退化为$O(n^2)$，空间复杂度会退化为$O(n)$，该方法还是不能AC。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        return helper(heights, 0, heights.size());
    }

    int helper(vector<int>& heights, int start, int end)
    {
        if (start == end) return 0;
        if (start + 1 == end) return heights[start];

        int minIndex = start;                           //minIndex存放区间内最矮柱子的下标
        for (int i = start + 1; i < end; ++ i)
        {
            if (heights[i] < heights[minIndex])         //寻找区间内最矮的柱子
            {
                minIndex = i;
            }
        }

        int area = (end - start) * heights[minIndex];   //第一种情况，矩形通过这根最矮的柱子
        int left = helper(heights, start, minIndex);    //第二种情况，矩形在最矮柱子左侧
        int right = helper(heights, minIndex + 1, end); //第三种情况，矩形在最矮柱子右侧

        return max(area, max(left, right));             //取三种情况的最大值
    }
};

3、单调栈

以某根柱子为顶的最大矩形，一定是从该柱子向两侧延伸直到遇到比它矮的柱子，这个最大矩形的高是该柱子的高，最大矩形的宽是它两侧比它矮的柱子中间的间隔：

1. 用一个栈保存直方图中的柱子的下标，并且栈中的柱子是递增排序的；
2. 遍历数组中的柱子，若当前柱子高度大于栈顶柱子高度，则当前柱子入栈，否则栈顶柱子出栈，并计算以位于栈顶的柱子为顶的最大矩形面积；
3. 数组遍历完后若栈中还剩下柱子，则剩余的这些柱子的右侧都没有比它们更矮的柱子了，它所代表的最大矩形宽度就是数组长度减去栈顶柱子的下标。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> stk;
        stk.push(-1);   //第一根柱子的下标是0，所以第一根柱子左侧的下标应该是-1

        int maxArea = 0;
        for (int i = 0; i < heights.size(); ++ i)
        {
            //栈不为空，且当前柱子高度小于栈顶柱子高度时，计算栈顶柱子所表示的矩形最大面积
            while (stk.top() != -1 && heights[stk.top()] > heights[i])
            {
                int height = heights[stk.top()];
                stk.pop();
                int width = i - stk.top() - 1;
                maxArea = max(maxArea, height * width);
            }

            stk.push(i);
        }

        //遍历一遍后，若栈中还有剩余的柱子，则表示它们右侧已经没有更矮的柱子了
        while (stk.top() != -1)
        {
            int height = heights[stk.top()];
            stk.pop();
            int width = heights.size() - stk.top() - 1;
            maxArea = max(maxArea, height * width);
        }

        return maxArea;
    }
};