一、题目

1、题目描述

给定 $n$ 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例1：

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例2：

输入： heights = [2,4]
输出： 4

2、基础框架

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {

    }
};

3、原题链接

84. 柱状图中最大的矩形

二、解题报告

1、思路分析

例子：

那么最大的长方形面积是如下图中的红色区域：

整体思路就是 必须以每个位置的直方图作为高的长方形能扩多远，遇到相同的高度时进行错化处理，最终是能计算正确的。

如何找到以每个位置的直方图作为高的长方形能扩充的范围呢？

找到每个位置左右最近的比它矮的直方图，除了这两个位置不能到达，其他位置就是它所能扩充的范围。

2、时间复杂度

$O(n)$

3、代码详解

• C++版

//不使用系统stack的解法
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if (heights.size() == 0) return 0;

        int n = heights.size();

        int _stack[n]; //准备一个栈，此处使用数组替代系统栈
        memset(_stack, 0, sizeof(_stack));

        int si = -1;

        int ans = 0;

        for (int i = 0; i < n; i++) {
            while (si != -1 && heights[_stack[si]] >= heights[i]) { //栈不为空 且 栈顶元素对应的值>=当前元素位置对应的值
                int cur = heights[_stack[si--]]; //获取栈顶位置的直方图高度
                int left = si == -1 ? -1 : _stack[si]; //找到左边最近的比栈顶位置直方图低的位置
                ans = max(ans, (i - left - 1) * cur); //右边最近的比栈顶位置直方图低的是i位置
                //所以以cur为高度的长方形能扩充的范围就是[left + 1, i - 1],宽度为(i - left - 1)
            }
            _stack[++si] = i;
        }

        while (si != -1) { //遍历完数组后，栈中还有数据，则单独结算
            int cur = heights[_stack[si--]];
            int left = si == -1 ? -1 : _stack[si];
            ans = max(ans, (n - left - 1) * cur);
        }

        return ans;
    }
};

//使用系统stack的解法
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if (heights.size() == 0) return 0;

        stack<int> sta;
        int area = 0;
        for (int i = 0; i < heights.size(); i++) {
            while (!sta.empty() && heights[sta.top()] >= heights[i]) {
                int j = sta.top();
                sta.pop();
                int k = sta.empty() ? -1 : sta.top();
                area = max(area, (i - k - 1) * heights[j]);
            }
            sta.push(i);
        }

        while (!sta.empty()) {
            int j = sta.top();
            sta.pop();
            int k = sta.empty() ? -1 : sta.top();
            int curArea = (heights.size() - k - 1) * heights[j];
            area = max(area, curArea);
        }
        return area;
    }
};

• Java 版

public class LargestRectangleInHistogram {
	//使用系统栈
	public static int largestRectangleArea1(int[] height) {
		if (height == null || height.length == 0) {
			return 0;
		}
		int maxArea = 0;
		Stack<Integer> stack = new Stack<Integer>();
		for (int i = 0; i < height.length; i++) {
			while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {
				int j = stack.pop();
				int k = stack.isEmpty() ? -1 : stack.peek();
				int curArea = (i - k - 1) * height[j];
				maxArea = Math.max(maxArea, curArea);
			}
			stack.push(i);
		}
		while (!stack.isEmpty()) {
			int j = stack.pop();
			int k = stack.isEmpty() ? -1 : stack.peek();
			int curArea = (height.length - k - 1) * height[j];
			maxArea = Math.max(maxArea, curArea);
		}
		return maxArea;
	}
	
	//使用数组替代系统栈
	public static int largestRectangleArea2(int[] height) {
		if (height == null || height.length == 0) {
			return 0;
		}
		int N = height.length;
		int[] stack = new int[N];
		int si = -1;
		int maxArea = 0;
		for (int i = 0; i < height.length; i++) {
			while (si != -1 && height[i] <= height[stack[si]]) {
				int j = stack[si--];
				int k = si == -1 ? -1 : stack[si];
				int curArea = (i - k - 1) * height[j];
				maxArea = Math.max(maxArea, curArea);
			}
			stack[++si] = i;
		}
		while (si != -1) {
			int j = stack[si--];
			int k = si == -1 ? -1 : stack[si];
			int curArea = (height.length - k - 1) * height[j];
			maxArea = Math.max(maxArea, curArea);
		}
		return maxArea;
	}
}