题目描述（困难难度）

84. Largest Rectangle in Histogram - 图1

给一个柱状图，输出一个矩形区域的最大面积。

解法一 暴力破解

以题目给出的例子为例，柱形图高度有 1, 2, 3, 5, 6，我们只需要找出每一个高度对应的最大的面积，选出最大的即可。如果求高度为 3 的面积最大的，我们只需要遍历每一个高度，然后看连续的大于等于 3 的柱形有几个，如果是 n 个，那么此时的面积就是 3 * n。所以高度确定的话，我们只需要找连续的大于等于 3 的柱形个数，也就是高度。

  1. public int largestRectangleArea(int[] heights) {
  2.     HashSet<Integer> heightsSet = new HashSet<Integer>();
  3.     //得到所有的高度，也就是去重。
  4.     for (int i = 0; i < heights.length; i++) {
  5.         heightsSet.add(heights[i]);
  6.     }
  7.     int maxArea = 0;
  8.     //遍历每一个高度
  9.     for (int h : heightsSet) {
  10.         int width = 0;
  11.         int maxWidth = 1;
  12.         //找出连续的大于等于当前高度的柱形个数的最大值
  13.         for (int i = 0; i < heights.length; i++) {
  14.             if (heights[i] >= h) {
  15.                 width++;
  16.             //出现小于当前高度的就归零，并且更新最大宽度
  17.             } else {
  18.                 maxWidth = Math.max(width, maxWidth);
  19.                 width = 0;
  20.             }
  21.         }
  22.         maxWidth = Math.max(width, maxWidth);
  23.         //更新最大区域的面积
  24.         maxArea = Math.max(maxArea, h * maxWidth);
  25.     }
  26.     return maxArea;
  27. }

时间复杂度：O（n²）。

空间复杂度：O ( n）。存所有高度。

解法二

参考这里。有一些快排的影子，大家不妨先去回顾一下快排。快排中，我们找了一个基准点，把数组分成了小于基准点的数，和大于基准点的数。然后递归的完成了排序。

类似的，这里我们也可以找一个柱子。然后把所有柱子分成左半区域和右半区域。

84. Largest Rectangle in Histogram - 图2

这样要找的最大矩形区域就是三种情况了。

  1. 最大矩形区域在不包含选定柱子的左半区域当中。
  2. 最大矩形区域在不包含选定柱子的右半区域当中。
  3. 最大矩形区域包含选定柱子的区域。

对于 1、2 两种情况，我们只需要递归的去求就行了。而对于第 3 种情况，我们找一个特殊的柱子作为分界点以方便计算，哪一个柱子呢？最矮的那个！有什么好处呢？这样包含该柱子的最大区域，一定是涵盖了当前所有柱子。

84. Largest Rectangle in Histogram - 图3

所以面积当然是当前选定柱子的高度乘以当前的最大宽度了。

对于当前的时间复杂度，如果每次选定的柱子都可以把区域一分为二，递推式就是

T（n） = 2 * T（n / 2 ) + n。

上边多加的 n 是找最小柱子耗费，因为需要遍历一遍柱子。然后和快排一样，这样递归下去，时间复杂度就是 O（n log（n））。当然和快排一样的问题，最坏的情况，如果最小柱子每次都出现在末尾，这样会使得只有左半区域，右半区域是 0。递推式就变成了

T（n） = T（n - 1 ) + n。

时间复杂度就变成 O（n²）了，怎么优化呢？

重点就在上边找最小柱子多加的 n 上了，如果我们找最小柱子时间复杂度优化成 log（n）。那么在最坏情况下，递推式变成

T（n） = T（n - 1 ) + log（n）。

最坏的情况，递推式代入，依旧是 O（n log（n））。而找最小柱子，就可以抽象成，在一个数组区间内找最小值问题，而这个问题前人已经提出了一个数据结构，可以使得时间复杂度是 log（n），完美！名字叫做线段树，可以参考这里和线段树空间复杂度，我就不重复讲了。主要思想就是利用二叉树，使得查找时间复杂度变成了 O（log（n））。

我们以序列 { 5, 9, 7, 4 ,6, 1} 为例，线段树长下边的样子。节点的值代表当前区间内的最小值。

84. Largest Rectangle in Histogram - 图4

  1. class Node// 节点
  2. {
  3.     int start;// 区间的左端点
  4.     int end;// 区间的右端点
  5.     int data;// 该区间的最小值
  6.     int index; // 该节点最小值对应数组的下标
  8.     public Node(int start, int end)// 构造方法中传入左端点和右端点
  9.     {
  10.         this.start = start;
  11.         this.end = end;
  12.     }
  14. }
  16. class SegmentTree {
  17.     private int[] base;;// 给定数组
  18.     Node[] nodes;// 存储线段树的数组
  20.     public SegmentTree(int[] nums) {
  21.         base = new int[nums.length];
  22.         for (int i = 0; i < nums.length; i++) {
  23.             base[i] = nums[i];
  24.         }
  25.         //需要 4n 的空间，上边链接给出了原因
  26.         nodes = new Node[base.length * 4];
  27.     }
  29.     public void build(int index)// 构造一颗线段树，传入下标
  30.     {
  31.         Node node = nodes[index];// 取出该下标下的节点
  32.         if (node == null) {// 根节点需要手动创建
  33.             nodes[index] = new Node(0, this.base.length - 1);
  34.             node = nodes[index];
  35.         }
  36.         if (node.start == node.end) {// 如果这个线段的左端点等于右端点则这个点是叶子节点
  37.             node.data = base[node.start];
  38.             node.index = node.start;
  39.         } else { // 否则递归构造左右子树
  40.             int mid = (node.start + node.end) >> 1;// 现在这个线段的中点
  41.             nodes[(index << 1) + 1] = new Node(node.start, mid);// 左孩子线段
  42.             nodes[(index << 1) + 2] = new Node(mid + 1, node.end);// 右孩子线段
  43.             build((index << 1) + 1);// 构造左孩子
  44.             build((index << 1) + 2);// 构造右孩子
  45.             if (nodes[(index << 1) + 1].data <= nodes[(index << 1) + 2].data) {
  46.                 node.data = nodes[(index << 1) + 1].data;
  47.                 node.index = nodes[(index << 1) + 1].index;
  48.             } else {
  49.                 node.data = nodes[(index << 1) + 2].data;
  50.                 node.index = nodes[(index << 1) + 2].index;
  51.             }
  52.         }
  53.     }
  55.     public Node query(int index, int start, int end) {
  56.         Node node = nodes[index];
  57.         if (node.start > end || node.end < start)
  58.             return null;// 当前区间和待查询区间没有交集，那么返回一个极大值
  59.         if (node.start >= start && node.end <= end)
  60.             return node;// 如果当前的区间被包含在待查询的区间内则返回当前区间的最小值
  61.         Node left = query((index << 1) + 1, start, end);
  62.         int dataLeft = left == null ? Integer.MAX_VALUE : left.data;
  63.         Node right = query((index << 1) + 2, start, end);
  64.         int dataRight = right == null ? Integer.MAX_VALUE : right.data;
  65.         return dataLeft <= dataRight ? left : right;
  67.     }
  68. }
  69. class Solution {
  70.     public int largestRectangleArea(int[] heights) {
  71.         if (heights.length == 0) {
  72.             return 0;
  73.         }
  74.         //构造线段树
  75.         SegmentTree tree = new SegmentTree(heights);
  76.         tree.build(0);
  77.         return getMaxArea(tree, 0, heights.length - 1, heights);
  78.     }
  79.     /**
  80.      *  查询某个区间的最小值
  81.      * @param tree 构造好的线段树 
  82.      * @param start 待查询的区间的左端点
  83.      * @param end 待查询的区间的右端点
  84.      * @param heights 给定的数组
  85.      * @return 返回当前区间的矩形区域的最大值
  86.      */
  87.     private int getMaxArea(SegmentTree tree, int start, int end, int[] heights) {
  88.         if (start == end) {
  89.             return heights[start];
  90.         }
  91.         //非法情况，返回一个最小值，防止影响正确的最大值
  92.         if (start > end) {
  93.             return Integer.MIN_VALUE;
  94.         }
  95.         //找出最小的柱子的下标
  96.         int min = tree.query(0, start, end).index;
  97.         //最大矩形区域包含选定柱子的区域。
  98.         int area1 = heights[min] * (end - start + 1);
  99.         //最大矩形区域在不包含选定柱子的左半区域。
  100.         int area2 = getMaxArea(tree, start, min - 1, heights);
  101.         //最大矩形区域在不包含选定柱子的右半区域。
  102.         int area3 = getMaxArea(tree, min + 1, end, heights);
  103.         //返回最大的情况
  104.         return Math.max(Math.max(area1, area2), area3);
  105.     }
  106. }

时间复杂度：O（n log（n））。

空间复杂度：O（n），用来存储线段树。

解法三

参考这里，思考下解法二中遇到的问题，利用了类似快排的思想，最好情况的递推式是

T（n） = 2 * T（n / 2 ) + n。

就是 n log（n），但是由于分界点的柱子的选择，并不能总保证两部分的柱子数量均分。所以如果这个问题解决，那么我们就可以保证时间复杂度是 n log（n）了。如何让它均分呢？我们强行把它分成 3 部分呗。

84. Largest Rectangle in Histogram - 图5

  1. 左半区域，含有一半柱子，当然如果总数是奇数个，这里会多一个。

  2. 右半区域，含有一半柱子，当然如果总数是奇数个，这里会少一个。

  3. 包含最中间柱子的部分，最大区域一定会包含橙色部分，这样才会横跨两个区域。

情况 1、2 的最大区域面积可以用递归来解决，情况 3 的话，我们只要保证是 O（n），就满足了我们的递推式，从而保证时间复杂度是O（n log（n））。怎么做呢？

贪婪的思想，每次选两边较高的柱子扩展柱子。然后其实就是求出了 2 个柱子，3 个柱子，4 个柱子，5 个柱子…每种情况的最大值，然后选最大的就可以了。

  1. 初始的时候是两个柱子，记录此时的面积。

  2. 然后加 1 个柱子，选取两边较高的柱子，然后计算此时的面积，更新最大区域面积。

  3. 不停的重复过程 2 ，直到所有柱子遍历完

  1. public int largestRectangleArea(int[] heights) {
  2.     if (heights.length == 0) {
  3.         return 0;
  4.     }
  5.     return getMaxArea(heights, 0, heights.length - 1);
  6. }
  8. private int getMaxArea(int[] heights, int left, int right) {
  9.     if (left == right) {
  10.         return heights[left];
  11.     }
  12.     int mid = left + (right - left) / 2;
  13.     //左半部分
  14.     int area1 = getMaxArea(heights, left, mid);
  15.     //右半部分
  16.     int area2 = getMaxArea(heights, mid + 1, right);
  17.     //中间区域
  18.     int area3 = getMidArea(heights, left, mid, right);
  19.     //选择最大的
  20.     return Math.max(Math.max(area1, area2), area3);
  21. }
  23. private int getMidArea(int[] heights, int left, int mid, int right) { 
  24.     int i = mid;
  25.     int j = mid + 1;
  26.     int minH = Math.min(heights[i], heights[j]);
  27.     int area = minH * 2;
  28.     //向两端扩展
  29.     while (i >= left && j <= right) {
  30.         minH = Math.min(minH, Math.min(heights[i], heights[j]));
  31.         //更新最大面积
  32.         area = Math.max(area, minH * (j - i + 1));
  33.         if (i == left) {
  34.             j++;
  35.         } else if (j == right) {
  36.             i--;
  37.             //选择较高的柱子
  38.         } else if (heights[i - 1] >= heights[j + 1]) {
  39.             i--;
  40.         } else {
  41.             j++;
  43.         }
  44.     }
  45.     return area;
  46. }

时间复杂度：O（n log（n））。

空间复杂度：O（log（n）），压栈的空间。

解法四

参考这里-Java-solution-explained-(beats-96)>)。解法一暴力破解中，我们把所有矩形区域按高度依次求出来，选出了最大的。这里我们想另外一个分类方法。分别求出包含每个柱子的矩形区域的最大面积，然后选最大的。要包含这个柱子，也就是这个柱子是当前矩形区域的高度。也就是，这个柱子是当前矩形区域中柱子最高的。如下图中包含橙色柱子的矩形区域的最大面积。

84. Largest Rectangle in Histogram - 图6

求当前的矩形区域，我们只需要知道比当前柱子到左边第一个小的 leftLessMin 和到右边第一个小的 rightLessMin 两个柱子下标，就可以求出矩形的面积为 (rightLessMin - leftLessMin - 1) * 当前柱子高度。然后遍历每个柱子，按同样的方法求出矩形面积，选最大的就可以了。

现在的问题就是，怎么知道 rightLessMin 和 leftLessMin 。

我们可以用一个数组，leftLessMin[ ] 保存各自的左边第一个小的柱子。

  1. leftLessMin[0] = -1;//第一个柱子前边没有柱子，所以赋值为 -1，便于计算面积              
  2. for (int i = 1; i < heights.length; i++) {              
  3.     int p = i - 1;
  4.     //p 一直减少，找到第一个比当前高度小的柱子就停止
  5.     while (p >= 0 && height[p] >= height[i]) {
  6.         p--;
  7.     }
  8.     leftLessMin[i] = p;              
  9. }

上边的时间复杂度是 O（n²），我们可以进行优化。参考下边的图，当前柱子 i 比上一个柱子小的时候，因为我们是找比当前柱子矮的，之前我们进行减 1，判断上上个。但是我们之前已经求出了上一个柱子的 leftLessMin[ i - 1]，也就是第一个比上个柱子小的柱子，所以其实我们可以直接跳到 leftLessMin[ i - 1] 比较。因为从 leftLessMin[ i - 1] + 1到 i - 1 的柱子一定是比当前柱子 i 高的，所以可以跳过。

84. Largest Rectangle in Histogram - 图7

这样的话时间复杂度达到了O（n）。开始自己不理解，问了一下同学。其实证明的话，可以结合解法五，我们寻找 leftLessMin 其实可以看做压栈出栈的过程，每个元素只会被访问两次。

  1. int[] leftLessMin = new int[heights.length];
  2. leftLessMin[0] = -1;
  3. for (int i = 1; i < heights.length; i++) {
  4.     int l = i - 1;
  5.     //当前柱子更小一些，进行左移
  6.     while (l >= 0 && heights[l] >= heights[i]) {
  7.         l = leftLessMin[l];
  8.     }
  9.     leftLessMin[i] = l;
  10. }

求到右边第一个小的柱子同理，下边是完整的代码。

  1. public int largestRectangleArea(int[] heights) {
  2.     if (heights.length == 0) {
  3.         return 0;
  4.     }
  5.     //求每个柱子的左边第一个小的柱子的下标
  6.     int[] leftLessMin = new int[heights.length];
  7.     leftLessMin[0] = -1;
  8.     for (int i = 1; i < heights.length; i++) {
  9.         int l = i - 1;
  10.         while (l >= 0 && heights[l] >= heights[i]) {
  11.             l = leftLessMin[l];
  12.         }
  13.         leftLessMin[i] = l;
  14.     }
  16.     //求每个柱子的右边第一个小的柱子的下标
  17.     int[] rightLessMin = new int[heights.length];
  18.     rightLessMin[heights.length - 1] = heights.length;
  19.     for (int i = heights.length - 2; i >= 0; i--) {
  20.         int r = i + 1;
  21.         while (r <= heights.length - 1 && heights[r] >= heights[i]) {
  22.             r = rightLessMin[r];
  23.         }
  24.         rightLessMin[i] = r;
  25.     }
  27.     //求包含每个柱子的矩形区域的最大面积，选出最大的
  28.     int maxArea = 0;
  29.     for (int i = 0; i < heights.length; i++) {
  30.         int area = (rightLessMin[i] - leftLessMin[i] - 1) * heights[i];
  31.         maxArea = Math.max(area, maxArea);
  32.     }
  33.     return maxArea;
  34. }

时间复杂度：O（n），取决于找 leftLessMin [ i ] 的复杂度。

空间复杂度：O（n），保存每个柱子左边右边第一个小的柱子下标。

解法五 栈

参考这里。之前也遇到利用栈巧妙解题的，例如42题的解法五，和这道题的共同点就是配对问题。思路的话，本质上和解法四是一样的，可以先看下解法四，左边第一个小于当前柱子和右边第一个小于当前柱子是一对。通过它俩可以求出当前柱子的最大矩形区域。那么具体怎么操作呢？

遍历每个柱子，然后分下边几种情况。

  • 如果当前栈空，或者当前柱子大于栈顶柱子的高度，就将当前柱子的下标入栈
  • 当前柱子的高度小于栈顶柱子的高度。那么就把栈顶柱子出栈，当做解法四中的当前要求面积的柱子。而右边第一个小于当前柱子的下标就是当前在遍历的柱子，左边第一个小于当前柱子的下标就是当前新的栈顶。

遍历完成后，如果栈没有空。就依次出栈，出栈元素当做解法四中的要求面积的柱子，然后依次计算矩形区域面积。

84. Largest Rectangle in Histogram - 图8

结合图可以看一下，从头开始遍历，遍历柱子开始的时候都大于前一个柱子高度，所以依次入栈。直到遍历到橙色部分，栈顶元素出栈，计算包含栈顶柱子的矩形区域。而左边第一个小于要求柱子的就是新栈顶，右边第一个小于要求柱子的就是当前遍历柱子。

  1. public int largestRectangleArea(int[] heights) {
  2.     int maxArea = 0;
  3.     Stack<Integer> stack = new Stack<>();
  4.     int p = 0;
  5.     while (p < heights.length) {
  6.         //栈空入栈
  7.         if (stack.isEmpty()) {
  8.             stack.push(p);
  9.             p++;
  10.         } else {
  11.             int top = stack.peek();
  12.             //当前高度大于栈顶，入栈
  13.             if (heights[p] >= heights[top]) {
  14.                 stack.push(p);
  15.                 p++;
  16.             } else {
  17.                 //保存栈顶高度
  18.                 int height = heights[stack.pop()];
  19.                 //左边第一个小于当前柱子的下标
  20.                 int leftLessMin = stack.isEmpty() ? -1 : stack.peek();
  21.                 //右边第一个小于当前柱子的下标
  22.                 int RightLessMin = p;
  23.                 //计算面积
  24.                 int area = (RightLessMin - leftLessMin - 1) * height;
  25.                 maxArea = Math.max(area, maxArea);
  26.             }
  27.         }
  28.     }
  29.     while (!stack.isEmpty()) {
  30.         //保存栈顶高度
  31.         int height = heights[stack.pop()];
  32.         //左边第一个小于当前柱子的下标
  33.         int leftLessMin = stack.isEmpty() ? -1 : stack.peek();
  34.         //右边没有小于当前高度的柱子，所以赋值为数组的长度便于计算
  35.         int RightLessMin = heights.length;
  36.         int area = (RightLessMin - leftLessMin - 1) * height;
  37.         maxArea = Math.max(area, maxArea);
  38.     }
  39.     return maxArea;
  40. }

时间复杂度：O（n），因为对于每个柱子只会经历入栈出栈，所以最多 2n 次。

空间复杂度：O（n），栈的大小。

总

这道题经典呀，第一次用快排的思想去解决问题，太优雅了。另外通过对问题的挖掘，时间复杂度优化到 O（n），也是惊叹。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情