文章目录
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:
implSolution{pubfnlargest_rectangle_area(heights:Vec<i32>)->i32{letmut ans =0;letmut stack =vec![-1];let n = heights.len();(0..n).for_each(|i|{while stack.len()>1&& heights[*stack.last().unwrap()asusize]> heights[i]{// 栈中比当前位置高的那些待确定右边界的下标都可以确定右边界了
ans = ans.max(heights[stack.pop().unwrap()asusize]*(i asi32-1- stack.last().unwrap()));}// 入栈,等到能够确定右边界时处理
stack.push(i asi32);});while stack.len()>1{// 栈中剩余的都是右边没有更低的
ans = ans.max(heights[stack.pop().unwrap()asusize]*(n asi32-1- stack.last().unwrap()));}return ans;}}
go:
funclargestRectangleArea(heights []int)int{
max :=func(x, y int)int{if x > y {return x
}return y
}
ans :=0
n :=len(heights)
stack :=[]int{-1}for i :=0; i < n; i++{forlen(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)}forlen(stack)>1{// 栈中剩余的都是右边没有更低的
ans =max(ans, heights[stack[len(stack)-1]]*(n-1-stack[len(stack)-2]))// 出栈
stack = stack[:len(stack)-1]}return ans
}
c++:
classSolution{public:intlargestRectangleArea(vector<int>& heights){int ans =0;constint 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:
classSolution:deflargestRectangleArea(self, heights: List[int])->int:
ans =0
n =len(heights)
stack =[-1]for i inrange(n):whilelen(stack)>1and heights[stack[-1]]> heights[i]:# 比当前位置高的那些待确定右边界的下标都可以确定右边界了
ans =max(ans, heights[stack.pop()]*(i -1- stack[-1]))# 入栈,等到能够确定右边界时处理
stack.append(i)whilelen(stack)>1:# 栈中剩余的都是右边没有更低的
ans =max(ans, heights[stack.pop()]*(n -1- stack[-1]))return ans
java:
classSolution{publicintlargestRectangleArea(int[] heights){int ans =0;finalint n = heights.length;Deque<Integer> stack =newLinkedList<>();
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/ 博客原创~
本文转载自: https://blog.csdn.net/leyi520/article/details/133166907
版权归原作者 二当家的白帽子 所有, 如有侵权,请联系我们删除。
版权归原作者 二当家的白帽子 所有, 如有侵权,请联系我们删除。