柱状图中最大的矩形

题目要求

给定一个由 n 个非负整数组成的数组，这些整数表示一个柱状图中每个柱子的高度，每个柱子的宽度假定为 1。要求计算在这个柱状图中，能够勾勒出的最大矩形的面积。

解题思路

要解决这个问题，我们可以采用以下几种思路：

暴力法：
- 遍历每对柱子，以较短的柱子为高，两柱子之间的距离为宽，计算出所有可能的矩形的面积。
- 在所有计算出的面积中找到最大值。
- 这种方法的时间复杂度较高，在最坏的情况下为 O(n^2)。
分治法：
- 找到最短的柱子，这个柱子将图分割为左右两部分。
- 最大矩形要么在左边，要么在右边，要么跨过最短的柱子。
- 递归地在左右两部分中寻找最大矩形，并与跨过最短柱子的矩形面积比较。
- 分治法的时间复杂度通常为 O(n log n)，但在最坏情况下（数组已排序）仍然可能是 O(n^2)。
栈的应用：
- 使用一个栈来维护一个索引序列，这些索引对应的柱子的高度是非递减的。
- 遍历每个柱子：
  - 如果当前柱子的高度大于栈顶索引对应的柱子的高度，将当前索引入栈。
  - 如果当前柱子的高度小于栈顶索引对应的柱子的高度，则说明找到了一个局部最大的矩形，其高为栈顶索引对应的柱子的高度，宽为当前索引与栈顶索引之间的距离。此时，计算这个矩形的面积，并将栈顶元素出栈，重复这个过程，直到栈顶索引对应的柱子的高度小于或等于当前柱子的高度。
  - 遍历完成后，栈中可能还有一些索引，这些对应的柱子的高度从栈底到栈顶是递增的。对于栈中的每个索引，其对应的矩形的宽可以认为是从该索引到数组末尾的距离。
- 这种方法的时间复杂度为 O(n)，因为每个索引最多入栈和出栈一次。

通过以上任一种方法，我们都可以找到柱状图中能够勾勒出的最大矩形的面积。通常情况下，栈的应用方法因为其线性的时间复杂度而被优先考虑。

Golang 版本

package main

import "fmt"

func largestRectangleArea(heights []int) int {
    maxArea := 0
    stack := []int{-1} // 初始化栈，先放入一个哨兵元素

    for i, height := range heights {
        for len(stack) > 1 && heights[stack[len(stack)-1]] >= height {
            // 计算面积
            h := heights[stack[len(stack)-1]]
            stack = stack[:len(stack)-1] // 出栈
            w := i - stack[len(stack)-1] - 1
            maxArea = max(maxArea, h*w)
        }
        stack = append(stack, i) // 当前柱子的索引入栈
    }

    // 清空栈中剩余的元素
    for len(stack) > 1 {
        h := heights[stack[len(stack)-1]]
        stack = stack[:len(stack)-1]
        w := len(heights) - stack[len(stack)-1] - 1
        maxArea = max(maxArea, h*w)
    }

    return maxArea
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func main() {
    heights := []int{2, 1, 5, 6, 2, 3}
    fmt.Println(largestRectangleArea(heights))
}

这段代码实现了使用栈的方法来解决柱状图中最大矩形面积的问题。代码首先定义了一个largestRectangleArea函数，该函数接收一个整数切片heights作为输入，返回一个整数表示最大矩形的面积。在main函数中，我们定义了一个示例输入，调用largestRectangleArea函数，并打印出结果。

C++版本

#include <iostream>
#include <vector>
#include <stack>

int largestRectangleArea(std::vector<int>& heights) {
    int maxArea = 0;
    std::stack<int> indexStack;
    indexStack.push(-1); // 添加一个哨兵，简化边界情况的处理

    for (int i = 0; i < heights.size(); ++i) {
        while (indexStack.top() != -1 && heights[indexStack.top()] >= heights[i]) {
            int height = heights[indexStack.top()];
            indexStack.pop();
            int width = i - indexStack.top() - 1;
            maxArea = std::max(maxArea, height * width);
        }
        indexStack.push(i);
    }

    // 清理栈中剩余的元素
    while (indexStack.top() != -1) {
        int height = heights[indexStack.top()];
        indexStack.pop();
        int width = heights.size() - indexStack.top() - 1;
        maxArea = std::max(maxArea, height * width);
    }

    return maxArea;
}

int main() {
    std::vector<int> heights = {2, 1, 5, 6, 2, 3};
    std::cout << largestRectangleArea(heights) << std::endl;
    return 0;
}

这段 C++代码实现了一个函数largestRectangleArea，它接受一个整数向量heights作为输入，并返回一个整数表示柱状图中最大矩形的面积。在main函数中，我们定义了一个示例输入，调用largestRectangleArea函数，并打印出结果。代码中使用了std::stack来维护索引的栈，以及std::max来计算最大面积。

Python 版本

def largestRectangleArea(heights):
    stack = [-1]
    max_area = 0

    for i, h in enumerate(heights):
        while stack[-1] != -1 and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            width = i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    while stack[-1] != -1:
        height = heights[stack.pop()]
        width = len(heights) - stack[-1] - 1
        max_area = max(max_area, height * width)

    return max_area

# Example usage:
if __name__ == "__main__":
    heights = [2, 1, 5, 6, 2, 3]
    print(largestRectangleArea(heights))

这段 Python 代码定义了一个函数largestRectangleArea，它接受一个列表heights作为输入，并返回一个整数表示柱状图中最大矩形的面积。在主函数中，我们定义了一个示例输入，调用largestRectangleArea函数，并打印出结果。代码中使用了列表来模拟栈的操作。

Java 版本

import java.util.Stack;

public class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int maxArea = 0;

        for (int i = 0; i < heights.length; ++i) {
            while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
                int height = heights[stack.pop()];
                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }

        while (stack.peek() != -1) {
            int height = heights[stack.pop()];
            int width = heights.length - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }

        return maxArea;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] heights = {2, 1, 5, 6, 2, 3};
        System.out.println(solution.largestRectangleArea(heights));
    }
}

这段 Java 代码定义了一个名为Solution的类，其中包含一个方法largestRectangleArea，它接受一个整数数组heights作为输入，并返回一个整数表示柱状图中最大矩形的面积。在main方法中，我们创建了一个Solution对象，定义了一个示例输入，调用largestRectangleArea方法，并打印出结果。代码中使用了Stack<Integer>来维护索引的栈。

Rust 版本

fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
    let mut stack: Vec<i32> = vec![-1]; // 使用-1作为哨兵值
    let mut max_area = 0;
    for (i, &height) in heights.iter().enumerate() {
        while *stack.last().unwrap() != -1 && heights[*stack.last().unwrap() as usize] >= height {
            let h = heights[stack.pop().unwrap() as usize];
            let w = i as i32 - stack.last().unwrap() - 1;
            max_area = max_area.max(h * w);
        }
        stack.push(i as i32);
    }

    while *stack.last().unwrap() != -1 {
        let h = heights[stack.pop().unwrap() as usize];
        let w = heights.len() as i32 - stack.last().unwrap() - 1;
        max_area = max_area.max(h * w);
    }

    max_area
}

fn main() {
    let heights = vec![2, 1, 5, 6, 2, 3];
    println!("{}", largest_rectangle_area(heights));
}

这段 Rust 代码定义了一个函数largest_rectangle_area，它接受一个整数向量heights作为输入，并返回一个整数表示柱状图中最大矩形的面积。在main函数中，我们定义了一个示例输入，调用largest_rectangle_area函数，并打印出结果。代码中使用了向量来模拟栈的操作，并利用 Rust 的模式匹配和所有权系统来确保代码的安全性。

总结

解决这个柱状图中最大矩形面积的问题，我们采用了一个单调栈的数据结构来优化查找过程。单调栈是一种特殊的栈，它在这个问题中用来维护一个索引序列，这些索引对应的柱子高度是单调递增的。

算法的主要步骤如下：

初始化一个栈，并将一个哨兵值（通常是-1）压入栈中，表示栈的底部。
遍历输入数组heights中的每个元素：
- 当栈不为空且当前元素小于栈顶索引对应的元素时，说明找到了一个局部最大矩形。此时，可以弹出栈顶元素，并计算以该栈顶元素为高的矩形面积（宽度为当前索引与新的栈顶索引之间的距离）。
- 将当前索引压入栈中。
遍历完成后，栈中可能还有一些元素。这些元素对应的柱子没有右边界，因此需要分别计算以这些柱子为高的矩形面积，直到栈为空。
在每一步中，计算出的矩形面积与当前最大面积进行比较，并更新最大面积。

这种方法的时间复杂度是 O(n)，因为每个元素最多被压入和弹出栈一次。空间复杂度是 O(n)，用于存储栈中的索引。

在实际代码实现中，我们需要注意栈操作的细节，以及在栈为空时如何处理。在 Rust 版本中，我们还需要注意所有权和生命周期的问题，确保代码的安全性。

hot-100