leetCode 84.Largest Rectangle in Histogram (最大矩形直方图) 解题思路和方法
2024-08-23 19:55:59
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3]
.
The largest rectangle is shown in the shaded area, which has area = 10
unit.
For example,
Given height = [2,1,5,6,2,3]
,
return 10
.
思路:此题还是有一些难度的,刚開始想的双指针。前后扫描,可是每次求最小的高度的时候都须要遍历一次,效率上不是非常高。为o(n2)。
代码例如以下:
public class Solution {
public int largestRectangleArea(int[] height) { int max = 0;//最大值
int i = 0;//左指针
int j = height.length - 1;//右指针
boolean isMinChange = true; //双指针扫描
while(i <= j){
int minHeight = Integer.MAX_VALUE;//范围内最小值
if(isMinChange){//最小值是否改变
isMinChange = false;
//又一次得到最小值
for(int k = i ; k <= j;k++){
if(height[k] < minHeight){
minHeight = height[k];
}
}
}
//面积
int area = (j - i + 1)*minHeight;
if(max < area){
max = area;
}
if(i == j){//假设相等,则结束
break;
}
if(height[i] < height[j]){//左指针添加,直到比当前大
int k = i;
while(k <= j && height[k] <= height[i]){
if(height[k] == minHeight){//推断最小值是否改变
isMinChange = true;
}
k++;
}
i = k;
}else{//右指针减小,直到比当前大
int k = j;
while( k >= i && height[k] <= height[j]){
if(height[k] == minHeight){//推断最小值是否改变
isMinChange = true;
}
k--;
}
j = k;
}
}
return max;
}
}
解法上过不了OJ,所以仅仅能在网上參看资料。最后找到资料例如以下。是用栈解决的。
public class Solution {
public int largestRectangleArea(int[] height) {
if (height == null || height.length == 0) return 0; Stack<Integer> stHeight = new Stack<Integer>();
Stack<Integer> stIndex = new Stack<Integer>();
int max = 0; for(int i = 0; i < height.length; i++){
if(stHeight.isEmpty() || height[i] > stHeight.peek()){
stHeight.push(height[i]);
stIndex.push(i);
}else if(height[i] < stHeight.peek()){
int lastIndex = 0;
while(!stHeight.isEmpty() && height[i] < stHeight.peek()){
lastIndex = stIndex.pop();
int area = stHeight.pop()*(i - lastIndex);
if(max < area){
max = area;
}
}
stHeight.push(height[i]);
stIndex.push(lastIndex);
}
}
while(!stHeight.isEmpty()){
int area = stHeight.pop()*(height.length - stIndex.pop());
max = max < area ? area:max;
} return max;
}
}
最新文章
- 纯前端JSON文件编辑器[0]
- maven2 com.jhlabs.imaging 01012005 maven安装jar包imaging命令
- 记一个PowerShell的方法调用 --ResolveWindowsPrincipal
- struts2-json-plugin插件实现异步通信
- struts2-获取WEB资源
- linux-CentOS6.4下安装oracle11g详解
- 【SQL】查询语句中in和exists的区别
- 《Pointers On C》读书笔记(第二章 基本概念)
- JS中的函数传参
- 怎样共享windows和linux之间的文件
- [CF364D]Ghd
- 剑指offer 8.递归和循环 跳台阶
- 【数据分析】线性回归与逻辑回归(R语言实现)
- toolbar按钮添加图标
- 桌面图标未读消息(小米,sony,三星手机)
- CVE-2017-8570漏洞利用
- spring 事务传播 never 当一个业务方法设置为never时候表示 不会加入任何事务中
- RHEL7体验KVM虚拟机
- Nginx 安装 --编译模块参数
- [转帖]windows 2008 Server R2 /Win7启用TLS 1.2