柱状图中最大的矩形

题面

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

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

示例 1:

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

示例 2：

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

提示：

• 1 <= heights.length <=105
• 0 <= heights[i] <= 104

分析

• 参考视频：单调栈【基础算法精讲 26】

• 首先，面积最大矩形的高度一定是 $\textit{heights}$ 中的元素，这可以用反证法证明：假如高度不在 $\textit{heights}$ 中，比如 $4$，那可以增加高度直到触及某根柱子的顶部，比如增加到 $5$，由于矩形底边长不变，高度增加，得到了面积更大的矩形，矛盾，所以面积最大矩形的高度一定是 $\textit{heights}$ 中的元素

• 枚举每个 $h=\textit{heights}[i]$，作为矩形的高。那么矩形的宽最大是多少？需要知道：

  • 在 $i$ 左侧的小于 $h$ 的最近元素的下标 $\textit{left}$，如果不存在则为 $-1$。求出了 $\textit{left}$，那么 $\textit{left}+1$ 就是矩形最左边那根柱子。如果 $\textit{left}=-1$，那么加一后是 $0$，就是整个 $\textit{heights}$ 最左边的柱子。
  • 在 $i$ 右侧的小于 $h$ 的最近元素的下标 $\textit{right}$，如果不存在则为 $n$。求出了 $\textit{right}$，那么 $\textit{right}-1$ 就是矩形最右边那根柱子。如果 $\textit{right}=n$，那么减一后是 $n-1$，就是整个 $\textit{heights}$ 最右边的柱子。

• 比如示例 1，选择 $i=2$ 这个柱子作为矩形的高，那么左边小于 $\textit{heights}[2]=5$ 的最近元素的下标为 $\textit{left}=1$，右边小于 $\textit{heights}[2]=5$ 的最近元素的下标为 $\textit{right}=4$。矩形的宽就是 $\textit{right}-\textit{left}-1 = 4-1-1=2$，矩形面积为 $h\cdot (\textit{right}-\textit{left}-1) = 5\cdot 2 = 10$

• 枚举 $i$，计算对应的矩形面积，更新答案的最大值

• 为什么这样做不会漏掉答案？题目本质是计算高×宽的最大值，高是枚举的，所以只要保证宽尽量大，答案就一定能被枚举计算到

• 如何快速计算 $\textit{left}$ 和 $\textit{right}$？可以用单调栈

• 使用单调栈，三次遍历，第一次找到左侧第一个更矮的柱子的下标，第一次找到右侧第一个更矮的柱子的下标，第三次遍历数组更新结果

  class Solution {
  public:
      int largestRectangleArea(vector<int> &heights) {
          int n = heights.size();
          vector<int> left(n, -1);
          stack<int> st;
          for (int i = 0; i < n; i++) {
              int h = heights[i];
              while (!st.empty() && heights[st.top()] >= h) {
                  st.pop();
              }
              if (!st.empty()) {
                  left[i] = st.top();
              }
              st.push(i);
          }
  
          vector<int> right(n, n);
          st = stack<int>();
          for (int i = n - 1; i >= 0; i--) {
              int h = heights[i];
              while (!st.empty() && heights[st.top()] >= h) {
                  st.pop();
              }
              if (!st.empty()) {
                  right[i] = st.top();
              }
              st.push(i);
          }
  
          int ans = 0;
          for (int i = 0; i < n; i++) {
              ans = max(ans, heights[i] * (right[i] - left[i] - 1));
          }
          return ans;
      }
  };

两次遍历法

• 继续优化，为了做到两次遍历，以及下面的一次遍历，首先，把 $\textit{right}[i]$ 的定义略作修改，调整为：在 $i$ 右侧的小于或等于 $h=\textit{heights}[i]$ 的最近元素的下标

• 如果 $\textit{heights}$ 中没有相同的元素，这样修改不影响 $\textit{right}[i]$

• 如果 $\textit{heights}$ 中有相同的元素呢？比如 $\textit{heights}=[1,3,4,3,2]$，左边那个 $3$ 的 $\textit{right}[i]$ 会变小，导致矩形面积变小，这是否会导致计算错误？

• 不会。注意在这种情况下，这两个高为 $3$ 的柱子，对应的矩形面积（在写法一中）是一样大的，虽然（在写法二中）左边那个 $3$ 的矩形面积变小了，但右边那个 $3$ 的矩形面积是不变的，所以不会错过正确答案

• 修改 $\textit{right}[i]$ 的定义后，可以把 $\textit{left}$ 和 $\textit{right}$ 合在一起计算，从而减少一次遍历：

• 在计算 $\textit{left}$ 的过程中，如果栈顶元素 $\ge\textit{heights}[i]$，那么 $i$ 就是栈顶元素的 $\textit{right}$​

• 代码实现

  class Solution {
  public:
      int largestRectangleArea(vector<int> &heights) {
          int n = heights.size();
          vector<int> left(n, -1);
          vector<int> right(n, n);
          stack<int> st;
          for (int i = 0; i < n; i++) {
              int h = heights[i];
              while (!st.empty() && heights[st.top()] >= h) {
                  right[st.top()] = i;
                  st.pop();
              }
              if (!st.empty()) {
                  left[i] = st.top();
              }
              st.push(i);
          }
  
          int ans = 0;
          for (int i = 0; i < n; i++) {
              ans = max(ans, heights[i] * (right[i] - left[i] - 1));
          }
          return ans;
      }
  };

一次遍历法

• 两次遍历法告诉我们，栈顶出栈时，当前下标就是栈顶的 $\textit{right}$

• 如果此刻能顺带求出栈顶的 $\textit{left}$，那不就能一步到位，一次遍历就搞定了？

• 想一想，栈顶的 $\textit{left}$ 在哪？

• 由于单调栈是底小顶大的，栈顶下面那个柱子的高度一定比栈顶小，所以栈顶下面的值就是 $\textit{left}$。

• 为简化代码逻辑，可以在一开始把 $-1$ 入栈，当作哨兵。当栈中只有一个数的时候，栈顶下面那个数刚好就是 $-1$，对应 $\textit{left}[i]=-1$ 的情况

• 此外，循环结束的时候，栈中还有数据，这些数据也要计算矩形面积。处理这种情况可以再写一个循环，但更简单的办法是，往 $\textit{heights}$ 的末尾加一个 $-1$（或者任意 $\le \min(\textit{heights})$​ 的数），从而保证循环结束的时候，栈一定是空的（不包括哨兵）

• 代码实现

  class Solution {
  public:
      int largestRectangleArea(vector<int>& heights) {
          heights.push_back(-1); // 最后大火收汁，用 -1 把栈清空
          stack<int> st;
          st.push(-1); // 在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况
          int ans = 0;
          for (int right = 0; right < heights.size(); right++) {
              int h = heights[right];
              while (st.size() > 1 && heights[st.top()] >= h) {
                  int i = st.top(); // 矩形的高（的下标）
                  st.pop();
                  int left = st.top(); // 栈顶下面那个数就是 left
                  ans = max(ans, heights[i] * (right - left - 1));
              }
              st.push(right);
          }
          return ans;
      }
  };