1
2
3

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

1
2

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 单调栈
    /// 1. 对于heights中的每一个heights[i], 最大面积矩形为: `heights[i] * ( right[i] - left[i] + 1 )`,
    ///    题目需要找出所有这些面积中最大的, 即 `max(heights[i] * (right[i] - left[i] + 1) )`.
    ///    其中:
    ///    - right[i]为当前柱子向右找到的第一个小于heights[i]的柱子的下标;
    ///    - left[i]为当前柱子向左找到的第一个小于heights[i]的柱子的下标;
    /// 2. 为了求取right[i], left[i], 可使用单调栈;
    /// 3. 单调栈inc_stack: 用于记录从左->右遍历时,已经访问过的最大heights[i];
    /// 4. 左->右遍历heights时, 如果栈顶元素高度<当前矩形高度heights[i], 则直接将heights[i]入栈;
    /// 5. 否则,如果栈顶元素高度 > 当前元素高度heights[i],
    ///    则以栈顶元素大小为高的最大面积矩形, 右边界r为i, 左边界l为栈顶下一个元素,
    ///    该矩形最大面积为: h * (i - l - 1)
    pub fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
        let mut heights = heights;
        heights.push(0); // heights左右各增加一个0, 以方便统一处理遍历边界;
        heights.insert(0, 0);
        let mut inc_stack: Vec<usize> = Vec::with_capacity(heights.len());
        let mut max_area = 0;
        for (i, &hs) in heights.iter().enumerate() {
            while !inc_stack.is_empty() && hs < heights[*inc_stack.last().unwrap()] {
                let cur = inc_stack.pop().unwrap();
                let h = heights[cur]; // 栈顶元素高度
                let l = inc_stack.last().unwrap(); // 栈顶元素左边界为栈次顶元素id
                let r = i; // 栈顶元素右边界为当前元素id;
                max_area = max_area.max(h * ((r - l - 1) as i32));
            }
            // 此时栈中所有元素高度已经 < 当前遍历元素高度
            inc_stack.push(i); // 将当前高度id入栈
        }

        max_area
    }
}
// @lc code=end

struct Solution;