Java实现 LeetCode 84 柱状图中最大得矩形
2024-09-06 00:08:12
84. 柱状图中最大的矩形
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积,其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
class Solution {
/**
* 利用单调栈 求解,总体思路是 以柱子i高度为矩形高度时所能形成最大面积(利用性质找出第i个柱子向左边和右边遍历时第一个比它低的柱子)
* 单调栈定义:只存高度递增的柱子
* 性质
* 出栈时:
* 那么如果单调栈为空了:说明没有比这个柱子更低的了(矩形宽度为这根柱子的序号:左边沿为0)
* 如果单调栈不为空:说明栈里面的柱子高度都小,那么左边沿为栈顶柱子的序号
*
* 矩形右边沿为i 因为你出栈 就说明你比别人低了,这已经是你能达到的面积极限了.出栈记录面积
* **/
public static int largestRectangleArea(int[] heights) {
int heightn[] =new int[heights.length+1];
for (int i = 0; i < heights.length; i++) {
heightn[i] = heights[i];
}
heightn[heights.length] = 0; //最后增加个高度为0 的柱子,以便吧单调栈里面的都弹出去。
Deque<Integer> stack =new ArrayDeque<>(); //存储序号
int maxS=0;
for (int i = 0; i < heightn.length;i++) {
while (!stack.isEmpty() && heightn[i]<heightn[stack.peek()]){ //一直出栈 直到遇见小的
int temp=stack.pop();
//这里是递减数列得长度
maxS= Math.max(maxS,( ( stack.isEmpty()?i:(i-stack.peek()-1) )*heights[temp] ));
}
stack.push(i); //入栈
}
return maxS;
}
}
最新文章
- Q
- 基于Maven构建开发第一个Storm项目
- js判断客户端平台
- PHP 如何读取一个1G的文件大小
- Fragment懒加载
- 关于Spring AOP和IOC的一些总结
- Elasticsearch客户端大全 http://www.searchtech.pro/elasticsearch-clients
- AN ESAY HIT COUNTER
- DevExpress ASP.NET 使用经验谈(7)-ASPxTreeList控件使用
- android面试题 不仅仅是面试是一个很好的学习
- android fragment addToBackStack bug
- 一个小时学会MySQL数据库
- python自动化开发-[第七天]-面向对象
- HttpClient的用法
- 阿里云 ECS 监控报警设置
- image 和 barplot 的组合
- ie6 双边距问题
- 缓冲区溢出基础实践(二)——ROP 与 hijack GOT
- P2049 魔术棋子
- 利用Xilinx HLS实现LDPC译码器