84.柱状图中最大的矩形
- 84.柱状图中最大的矩形
- 题目
- 题解
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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。\
题解
柱子彼此相邻，宽度都为1，高度各不相同。对于当前柱子i来说，它所能勾勒出的矩形面积是由其左边柱子和右边柱子的高度共同决定的。
看了这道题完全没思路，这里从题解的如下思路开始做题。
如果其左边柱子的高度大于等于当前柱子的高度，则可以向左侧扩张，直到左边柱子高度小于当前柱子高度或左边再无其它柱子；同样的，如果其右边柱子的高度大于等于当前柱子的高度，则可以向右侧扩张，直到右边柱子高度小于等于当前柱子高度或右边再无其它柱子。
这时，就可以计算出以当前柱子高度为高，左右柱子间距离为宽的矩形面积。
作者：hardcore-aryabhata
链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/dong-hua-yan-shi-dan-diao-zhan-84zhu-zhu-03w3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
做出来之后这里进行补充别人的题解方便理解透彻，补充开始
感觉自己没有想出来是因为一来就看整个整体，没有举例假设针对某一个柱子，怎么求它能构成最大矩形的面积。
题目转化为：：依次遍历柱形的高度，对于每一个高度分别向两边扩散，求出以当前高度为矩形的最大宽度多少。
补充结束
所以我们需要找到当前柱子i的左右边界，第一个比它小的值。可以使用单调栈。
从栈底到栈顶 从小到大排列。
for(int i=0;i找到了右边第一个比它小的元素，那么左边第一个比它小的元素如何寻找？左边第一个比它小的在栈中一定在它的下一个位置。
for(int i=0;iresult) result = area;//更新最大值
}
st.push(i);
}
上述的情况是假设左右两边都能找到比他小的元素，如果只有一边找到了，或者两边都没有找到？
数组中是非负整数，那么可以手动的在开头和结尾添加一个0，0一定是小于其他整数的,这样对于每一个柱子一定可以找到它的左右边界。
class Solution {
public int largestRectangleArea(int[] heights) {
int result=0;
int area,right,left,cur;
Stack st = new Stack <>();
int [] newHeights = new int[heights.length + 2]; //新数组
newHeights[0] = 0;
newHeights[newHeights.length - 1] = 0;
for (int index = 0; index < heights.length; index++){
newHeights[index + 1] = heights[index];
}
st.push(0);
for(int i=1;iresult) result = area;//更新最大值
}
st.push(i);
}
return result;
}
}
复制数组System.arraycopy()
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
System中提供了一个native静态方法arraycopy(),可以使用这个方法来实现数组之间的复制,它是一个静态本地方法，由虚拟机实现，效率比用java一个个复制高。
对于一维数组来说，这种复制属性值传递，修改副本不会影响原来的值。对于二维或者一维数组中存放的是对象时，复制结果是一维的引用变量传递给副本的一维数组，修改副本时，会影响原来的数组。
native Java平台有个用户和本地C代码进行互操作的API，称为Java Native Interface (Java本地接口)。这里有时间再进行学习。
src:表示原数组
srcPos：表示原数组要复制的起始位置
dest：表示目标数组
destPos:目标数组开始的起始位置
length：表示要复制的长度
那么本道题可以写成
int [] newHeights = new int[heights.length + 2]; //新数组
//newHeights[0] = 0;
//newHeights[newHeights.length - 1] = 0;
//for (int index = 0; index < heights.length; index++){
//newHeights[index + 1] = heights[index];
//}
System.arraycopy(heights,0,newHeights,1,heights.length);