1. 题解

题目

链接🔗：84. Largest Rectangle in Histogram

BBJz0av

这道题和42. Trapping Rain Water有些相像，但是42题求的是能围住的最大面积，而本题求的是连成的矩阵的最大面积，因而在计算面积的方法上有些许不同。85. Maximal Rectangle就是在本题基础上的变式，通过一系列变化可以使用本题方法。

分析

简单分析可以知道最大矩形面积有两种情况：

当前矩形的高度heights[i] * 1
当前矩形的高度heights[i] * (向右第一个比当前高度小的矩形的index - 向左第一个比当前高度小的矩形的index - 1)

经过进一步归纳发现，第一种情况其实包含于第二种情况。

解法一：DP

根据上述描述，如果我们每次遍历到一个index，就可以知道左右需要的index，就可以直接计算最大面积。所以本题应该构建两个数组，来存储每一个index向左第一个较小矩形的index和向右第一个较小矩形的index的数组。

int[] leftLess = new int[heights.length];   // store the left index - i that heights[i] <= heights[current]
int[] rightLess = new int[heights.length];  // same to the leftLess
leftLess[0] = -1;
rightLess[heights.length - 1] = heights.length;
// leftLess
for (int i = 1; i < heights.length; ++i) {
  int j = i - 1;
  while (j >= 0 && heights[j] >= heights[i]) {
    // j--;
    // by replacing the above line with the following line
    // BTW: we need to change index boundary ...
    // we can change the complexity from O(N^2) to O(N)
    j = leftLess[j];
  }
  leftLess[i] = j;
}

// rightLess
for (int i = heights.length - 1; i >= 0; --i) {
  int j = i + 1;
  while (j < heights.length && heights[j] >= heights[i]) {
    // j++;
    j = rightLess[j];
  }
  rightLess[i] = j;
}

注意代码的第13行j = leftLess[j]和第23行j = rightLess[j];，使用了一个小trick，来跳过重复的情况，把时间复杂度由O(N^2)降到O(N)，否则可能出现TLE。

最后比较每一个index上能构成的矩阵的最大面积

int maxArea = 0;
for (int i = 0; i < heights.length; ++i) {
  maxArea = Math.max(maxArea, heights[i] * (rightLess[i] - leftLess[i] - 1));
}
return maxArea;

复杂度

时间：O(N)

空间：O(N)

解法二：Stack

核心思想类似解法一，但是我们不再存储左右index，而是使用stack来存储左边的index。stack中的index代表的height单调递增（严格递增），每当遇到比stack中peek()的height小的值就开始计算面积（遇到小的height，说明stack中存储的height已经达到当前最高）。

if (heights.length == 1) return heights[0];

// use stack to store the index of increasing heights
Deque<Integer> stack = new ArrayDeque<>();

int len = heights.length;
int maxArea = 0;

// notice we need i to be equal to len at last
for (int i = 0; i <= len; ++i) {
  while (!stack.isEmpty() && (i == len || heights[stack.peek()] >= heights[i])) {
    int h = heights[stack.pop()];   // the current highest in the stack
    int left = stack.isEmpty() ? -1 : stack.peek();
    maxArea = Math.max(maxArea, (i - 1 - left) * h);
  }
  // push index of increasing heights
  stack.push(i);
}
return maxArea;

直接看代码有些抽象，可以通过画图理解，但是本质思想是：如果遇到更高的就存储起来，如果遇到较低的就开始开始从stack中取index进行比较。因为遇到更高的意味着面积可能更大，遇到低的（或是把数组遍历完了）意味着遇到了面积的上限，需要计算比较了。

复杂度

时间：O(N)：因为stack里最多累计存储N个index，每个index最多被存储一次，所以每个index最多被访问两次，时间复杂度是O(2*N) = O(N)

空间：O(N)

2. 相关题目

42. Trapping Rain Water

ICqtwtw

这里简单提一下42. Trapping Rain Water的三种解法，细节不做展开：

参考自：https://www.youtube.com/watch?v=StH5vntauyQ

Brute Force；时间复杂度O(N^2)，空间复杂度O(1)
DP (prefix-max)：第一种方法中时间复杂度高只是因为每一次都在向一个元素的两侧重复寻找最大值，我们可以使用2个DP数组来记录最大值
Two Pointers：更进一步，每一次计算单格的蓄水量时，只需要单边（即最大值较小的一边的）

85. Maximal Rectangle

FVwNEL9

85. Maximal Rectangle看似需要用到DP table等技巧，但其实可以通过变化把问题抽象成84. Largest Rectangle in Histogram：

把每一行看成是histogram里的一个单位
从第一行开始开始构建histogram，并且需要在每次（每行构建完后）计算最大面积，每一行都放在同一个heights[]数组中，例如：heights = [3, 1, 3, 2, 2]，然后对该数组使用84题的stack或是dp
每次更新heights：如果matrix在当前(i, j) == 1，那么就heights[j]++，否则heights[j] = 0

复杂度

时间：O(row * col)

空间：O(col)