本文主要是介绍算法leetcode｜84. 柱状图中最大的矩形（rust重拳出击），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 84. 柱状图中最大的矩形：
- 样例 1：
- 样例 2：
- 提示：
- 分析：
- 题解：
- rust：
- go：
- c++：
- python：
- java：
84. 柱状图中最大的矩形：
给定 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
分析：
- 面对这道算法题目，二当家的再次陷入了沉思。
- 眼睛一看似乎有思路，但是一动手就容易不知如何下手。
- 双循环，遍历每个柱子，查找左边第一个低于自己的柱子，和右边第一个低于自己的柱子，这样就能算出当前柱子这个高度最大的宽度，有搞头，很明显会很慢，还有没有更好的办法呢。
- 找到每个柱子的左右边界（第一个低于自己的柱子）是关键，有没有办法降低查找的复杂度呢？
- 要是能一次遍历就把左右边界找到就好了，祭出神器单调栈，如果栈为空就入栈（这里可以使用技巧，让处理逻辑统一），否则判断下一个柱子如果高于栈顶或者和栈顶一样高也直接入栈，如果低于栈顶就出栈，因为当前这个柱子就是栈顶元素的右边界，重复这个过程，就可以在一次遍历的过程中就找到左右边界。
- 特别要注意遍历过程中栈为空，和遍历完所有柱子但是栈不为空的情况。
题解：
rust：
impl Solution {pub fn largest_rectangle_area(heights: Vec<i32>) -> i32 {let mut ans = 0;let mut stack = vec![-1];let n = heights.len();(0..n).for_each(|i| {while stack.len() > 1 && heights[*stack.last().unwrap() as usize] > heights[i] {// 栈中比当前位置高的那些待确定右边界的下标都可以确定右边界了ans = ans.max(heights[stack.pop().unwrap() as usize] * (i as i32 - 1 - stack.last().unwrap()));}// 入栈，等到能够确定右边界时处理stack.push(i as i32);});while stack.len() > 1 {// 栈中剩余的都是右边没有更低的ans = ans.max(heights[stack.pop().unwrap() as usize] * (n as i32 - 1 - stack.last().unwrap()));}return ans;}
}
go：
func largestRectangleArea(heights []int) int {max := func(x, y int) int {if x > y {return x}return y}ans := 0n := len(heights)stack := []int{-1}for i := 0; i < n; i++ {for len(stack) > 1 && heights[stack[len(stack)-1]] > heights[i] {// 栈中比当前位置高的那些待确定右边界的下标都可以确定右边界了ans = max(ans, heights[stack[len(stack)-1]]*(i-1-stack[len(stack)-2]))// 出栈stack = stack[:len(stack)-1]}// 入栈，等到能够确定右边界时处理stack = append(stack, i)}for len(stack) > 1 {// 栈中剩余的都是右边没有更低的ans = max(ans, heights[stack[len(stack)-1]]*(n-1-stack[len(stack)-2]))// 出栈stack = stack[:len(stack)-1]}return ans
}
c++：
class Solution {
public:int largestRectangleArea(vector<int>& heights) {int ans = 0;const int n = heights.size();stack<int> s;s.push(-1);for (int i = 0; i < n; ++i) {while (s.size() > 1 && heights[s.top()] > heights[i]) {// 栈中比当前位置高的那些待确定右边界的下标都可以确定右边界了int height = heights[s.top()];s.pop();ans = max(ans, height * (i - 1 - s.top()));}// 入栈，等到能够确定右边界时处理s.push(i);}while (s.size() > 1) {// 栈中剩余的都是右边没有更低的int height = heights[s.top()];s.pop();ans = max(ans, height * (n - 1 - s.top()));}return ans;}
};
python：
class Solution:def largestRectangleArea(self, heights: List[int]) -> int:ans = 0n = len(heights)stack = [-1]for i in range(n):while len(stack) > 1 and heights[stack[-1]] > heights[i]:# 比当前位置高的那些待确定右边界的下标都可以确定右边界了ans = max(ans, heights[stack.pop()] * (i - 1 - stack[-1]))# 入栈，等到能够确定右边界时处理stack.append(i)while len(stack) > 1:# 栈中剩余的都是右边没有更低的ans = max(ans, heights[stack.pop()] * (n - 1 - stack[-1]))return ansjava：
class Solution {public int largestRectangleArea(int[] heights) {int ans = 0;final int n = heights.length;Deque<Integer> stack = new LinkedList<>();stack.push(-1);for (int i = 0; i < n; ++i) {while (stack.size() > 1 && heights[stack.peek()] > heights[i]) {// 栈中比当前位置高的那些待确定右边界的下标都可以确定右边界了ans = Math.max(ans, heights[stack.pop()] * (i - 1 - stack.peek()));}// 入栈，等到能够确定右边界时处理stack.push(i);}while (stack.size() > 1) {// 栈中剩余的都是右边没有更低的ans = Math.max(ans, heights[stack.pop()] * (n - 1 - stack.peek()));}return ans;}
}
非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~
这篇关于算法leetcode｜84. 柱状图中最大的矩形（rust重拳出击）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
