HHot 100C++ 图解

84. 柱状图中最大的矩形

一句话套路单调递增栈 + 首尾 0 哨兵结算宽度

题目描述

给定 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

思路

时间O(n)
空间O(n)

思路

枚举「以某根柱子的高度为准」能撑多宽 —— 即左右第一个更矮的柱子在哪。

单调递增栈一次遍历搞定

当 h[i] 小于栈顶时弹出 t,弹出后新栈顶 left 就是 t 左边第一个更矮的位置,i 是右边第一个更矮的位置,于是宽度 = i - left - 1。

首尾各加一根 0 哨兵,免掉「栈空」和「收尾未结算」两种特判。

联动

Q85 最大矩形 = 把每一行当作柱状图的底,逐行调用本函数。

数值范围

高度 <= 10^4、n <= 10^5,面积最大 10^9,int 刚好装得下(2^31-1 ≈ 2.1×10^9);

范围再大一档(比如高度 10^5)就必须换 long long 了。

图解

6 0 7 1 5 2 2 3 4 4 5 5 9 6 3 7
数组(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 4

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/12_stack.cpp24 行
namespace lc0084 {
class Solution {
 public:
  int largestRectangleArea(vector<int>& heights) {
    vector<int> h;
    h.reserve(heights.size() + 2);
    h.push_back(0);  // 左哨兵:保证栈里永远有一个更矮的柱子
    for (int x : heights) h.push_back(x);
    h.push_back(0);  // 右哨兵:保证结束时全部结算完
    stack<int> st;   // 单调递增栈(存下标)
    int best = 0;
    for (int i = 0; i < (int)h.size(); ++i) {
      while (!st.empty() && h[i] < h[st.top()]) {
        int height = h[st.top()];
        st.pop();
        int left = st.top();  // 左边第一个更矮的
        best = max(best, height * (i - left - 1));
      }
      st.push(i);
    }
    return best;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q84_largest_rectangle_in_histogram13 行
lc0084::Solution s;
vector<int> a{2, 1, 5, 6, 2, 3};
CHECK_EQ(s.largestRectangleArea(a), 10);  // 高 5、宽 2(柱子 5 和 6)
vector<int> b{2, 4};
CHECK_EQ(s.largestRectangleArea(b), 4);
vector<int> c{1, 1, 1, 1};  // 等高要能连成一片
CHECK_EQ(s.largestRectangleArea(c), 4);
vector<int> d{6, 7, 5, 2, 4, 5, 9, 3};
CHECK_EQ(s.largestRectangleArea(d), 16);  // 高 2 撑满 8 根柱子;高>4 的最长段只有 3(→ 12)
vector<int> e{0};
CHECK_EQ(s.largestRectangleArea(e), 0);
vector<int> f{2, 1, 2};
CHECK_EQ(s.largestRectangleArea(f), 3);  // 高 1 × 宽 3(中间那根矮柱不阻断底边)

↑↓ 选择↵ 打开/ 随时唤起