题目描述（困难难度）

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

解法一暴力破解

以题目给出的例子为例，柱形图高度有 1, 2, 3, 5, 6，我们只需要找出每一个高度对应的最大的面积，选出最大的即可。如果求高度为 3 的面积最大的，我们只需要遍历每一个高度，然后看连续的大于等于 3 的柱形有几个，如果是 n 个，那么此时的面积就是 3 * n。所以高度确定的话，我们只需要找连续的大于等于 3 的柱形个数，也就是高度。 1. public int largestRectangleArea(int[] heights) { 2. HashSet heightsSet = new HashSet(); 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）。存所有高度。

解法二

参考这里。有一些快排的影子，大家不妨先去回顾一下快排。快排中，我们找了一个基准点，把数组分成了小于基准点的数，和大于基准点的数。然后递归的完成了排序。类似的，这里我们也可以找一个柱子。然后把所有柱子分成左半区域和右半区域。这样要找的最大矩形区域就是三种情况了。 1. 最大矩形区域在不包含选定柱子的左半区域当中。 2. 最大矩形区域在不包含选定柱子的右半区域当中。 3. 最大矩形区域包含选定柱子的区域。

对于 1、2 两种情况，我们只需要递归的去求就行了。而对于第 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} 为例，线段树长下边的样子。节点的值代表当前区间内的最小值。 1. class Node// 节点 2. { 3. int start;// 区间的左端点 4. int end;// 区间的右端点 5. int data;// 该区间的最小值 6. int index; // 该节点最小值对应数组的下标 7. 8. public Node(int start, int end)// 构造方法中传入左端点和右端点 9. { 10. this.start = start; 11. this.end = end; 12. } 13. 14. } 15. 16. class SegmentTree { 17. private int[] base;;// 给定数组 18. Node[] nodes;// 存储线段树的数组 19. 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. } 28. 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. } 54. 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; 66. 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 部分呗。 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. }
    7.   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. }
    22.   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++;
    42.   43.         }
    44.     }
    45.     return area;
    46. }

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

解法四

参考这里-Java-solution-explained-(beats-96)>)。解法一暴力破解中，我们把所有矩形区域按高度依次求出来，选出了最大的。这里我们想另外一个分类方法。分别求出包含每个柱子的矩形区域的最大面积，然后选最大的。要包含这个柱子，也就是这个柱子是当前矩形区域的高度。也就是，这个柱子是当前矩形区域中柱子最高的。如下图中包含橙色柱子的矩形区域的最大面积。求当前的矩形区域，我们只需要知道比当前柱子到左边第一个小的 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 高的，所以可以跳过。这样的话时间复杂度达到了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. } 15. 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. } 26. 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题的解法五，和这道题的共同点就是配对问题。思路的话，本质上和解法四是一样的，可以先看下解法四，左边第一个小于当前柱子和右边第一个小于当前柱子是一对。通过它俩可以求出当前柱子的最大矩形区域。那么具体怎么操作呢？遍历每个柱子，然后分下边几种情况。 * 如果当前栈空，或者当前柱子大于栈顶柱子的高度，就将当前柱子的下标入栈 * 当前柱子的高度小于栈顶柱子的高度。那么就把栈顶柱子出栈，当做解法四中的当前要求面积的柱子。而右边第一个小于当前柱子的下标就是当前在遍历的柱子，左边第一个小于当前柱子的下标就是当前新的栈顶。

遍历完成后，如果栈没有空。就依次出栈，出栈元素当做解法四中的要求面积的柱子，然后依次计算矩形区域面积。结合图可以看一下，从头开始遍历，遍历柱子开始的时候都大于前一个柱子高度，所以依次入栈。直到遍历到橙色部分，栈顶元素出栈，计算包含栈顶柱子的矩形区域。而左边第一个小于要求柱子的就是新栈顶，右边第一个小于要求柱子的就是当前遍历柱子。 1. public int largestRectangleArea(int[] heights) { 2. int maxArea = 0; 3. Stack 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. }