P146 直方图中的最大矩形

描述#

这个题目说的是，给你一个非负整数数组，数组中的整数表示直方图的高度，每个直方图的宽度都为 1，你要计算出直方图中最大矩形的面积。

比如说，给你的数组是 2, 1, 3, 4, 1, 它对应的直方图如图所示：
      +--+
      |  |
   +--+  |
   |  |  |

+--+  |  |  |
|  |  |  |  |
|  +--+  |  +--+
|  |  |  |  |  |
+--+--+--+--+--+-->
2  1  3  4  1
在这些直方图组成的区域里，可以形成的最大矩形是 3 和 4 这两个直方图中，高度为 3，宽度为 2 的矩形。它的面积为 6，因此你要返回 6。

代码#

public class AlgoCasts {

  // Time: O(n^2), Space: O(1)
  public int largestRectangleAreaExpand(int[] heights) {
    if (heights == null || heights.length == 0) return 0;
    int max = 0, n = heights.length;
    for (int i = 0; i < n; ++i) {
      int l = i, r = i;
      while (l >= 0 && heights[l] >= heights[i]) --l;
      while (r < n && heights[r] >= heights[i]) ++r;
      max = Math.max(max, heights[i] * (r - l - 1));
    }
    return max;
  }

  // Time: O(n), Space: O(n)
  public int largestRectangleAreaStack(int[] heights) {
    if (heights == null || heights.length == 0) return 0;
    int max = 0, n = heights.length;
    Stack<Integer> st = new Stack<>();
    for (int r = 0; r <= n; ++r) {
      int h = r == n ? 0 : heights[r];
      while (!st.empty() && h < heights[st.peek()]) {
        int idx = st.pop();
        int l = st.empty() ? -1 : st.peek();
        max = Math.max(max, heights[idx] * (r - l - 1));
      }
      st.push(r);
    }
    return max;
  }

  // 用数组模拟栈
  // Time: O(n), Space: O(n)
  public int largestRectangleAreaArray(int[] heights) {
    if (heights == null || heights.length == 0) return 0;
    int max = 0, n = heights.length, top = -1;
    int[] st = new int[n+1];
    for (int r = 0; r <= n; ++r) {
      int h = r == n ? 0 : heights[r];
      while (top != -1 && h < heights[st[top]]) {
        int idx = st[top--];
        int l = top == -1 ? -1 : st[top];
        max = Math.max(max, heights[idx] * (r - l - 1));
      }
      st[++top] = r;
    }
    return max;
  }

}