网站做贷款许可证,部队网站建设总结,建设了湛江市志愿服务网站,大兴网站建设首选公司柱状图中最大的矩形
题目链接 用什么数据结构#xff1f;
要得到柱状图中最大的矩形#xff0c;我们就必须要知道对于每一个高度heights[i]#xff0c;他所能勾勒出的矩形最大是多少#xff08;即宽度最大是多少#xff09;。
而对应到图上我们可以知道#xff0c;要知…柱状图中最大的矩形
题目链接 用什么数据结构
要得到柱状图中最大的矩形我们就必须要知道对于每一个高度heights[i]他所能勾勒出的矩形最大是多少即宽度最大是多少。
而对应到图上我们可以知道要知道最大宽度那就需要通过对下标的计算得到因此要存储的也应该是每个高度对应的下标。 即通过存储的下标索引找到对应的高度同时快速计算出宽度最终得到面积 我们就拿上面的例子进行分析 一开始遍历的柱形高度是2但以这一高度所确定的矩形还不能确定其面积的最大值因此继续遍历 第二个柱形高度为1此时这一高度所确定的最大矩形还不能确定。但是它前面的下标为0的柱形所确定的最大矩形就可以确定了。因为下标为1的这个柱形高度比下标为0的小矮的卡在了高的后面那么这个高的就不能向右扩展了。 这个时候我们也就能计算下标为0的这一高度所能确定的最大矩形的面积了。同时既然这一下标的高度已经确定我们也就可以忽略这一下标代表的高度了我们将其标灰。 第三个高度为5由同样的分析可得下标为2和下标为1的高度都不能确定其最大的矩形。继续遍历。 第四个高度为6同样高度为1,5,6的三个柱形也同样不能确定最大的矩形继续便利。 第五个高度为2小于下标为3的高度因此下标为3高度为6的柱形确定的最大矩形就知道了。面积size 6 * (4-2-1) 6同时由于这个柱形已经计算就将其忽略、标灰。 下标为4高度为2的柱形仍低于下标为2高度为5的柱形因此下标为2高度为5的柱形确定的最大矩形也就知道了。面积size 5 * (4-1-1) 10同时将这一柱形忽略、标灰。 下标为4高度为2的柱形高于下标为1高度为1的柱形因此这两个柱形仍不能确定其最大的矩形继续遍历。 第六个的高度为3由同样的分析高度为1,2,3的柱形都不能确定其最大的矩形
此时我们就遍历完了整个heights数组但是我们还有三个高度的最大矩形还没有确定为了处理这三个数据我们可以假设下标为6的柱形的高度为0小于1都可以 这样下标为5高度为3的柱形就被夹在了两个较矮柱形的中间其最大矩形也就确定了。size 3 * (6-4-1) 3 同理下标为4高度为2的矩形面积为size 2 * (6-1-1) 8 此时只剩下下标为1高度为1的柱形他是所有柱形中最低的柱形所以它最大矩形的宽度就是整个数组的长度因此面积size 1 * 6 6
至此每个柱形所确定的最大矩形都已经分析完毕。
由上面的分析我们可以得出以下结论
存储下标时我们是从左到右存储的但是计算下标对应的高度所确定的矩形面积时是从右向左计算的例如是先计算高度为6的面积在计算高度为5的面积这符合先入后出的特性因此这一题我们要用到的数据结构是栈。之所以能确定一个柱形的最大矩形就是在他右边碰到了比他更低的柱形因为这个更低的柱形限制了这个高柱形的扩张。因此这个栈存放的下标对应的高度应该是单调非递减的注意不是单调递增只要碰到递减的情况就说明可以计算栈顶元素所代表高度的矩形面积了。这个栈之所以要单调非递减时要考虑到进栈元素等于栈顶元素的情况。如下图 如果将栈设计为单调递增的那么当进栈元素5入栈时栈顶元素5就要出栈并计算其面积但问题是这个进栈元素5并不小于这个栈顶元素5那么这个栈顶元素5所确定的最大矩形也就不能确定。因此进栈元素等于栈顶元素时栈顶元素不要出栈。即这个栈为单调非递减的。
考虑特殊情况添加哨兵位
情况一计算宽度时栈空。如下图 此时栈中存储的下标为[0]进栈下标对应的高度小于栈顶元素对应的高度栈顶元素需要出栈并计算其高度对应的最大矩形。现在问题来了栈顶元素出栈后栈为空没有下标用来计算宽度这里就要用if(stackEmpty)来进行特殊处理但显然这是不方便的。因此我们可以在heights数组的最前面加入一个高度0这样我们就可以保证栈中始终留有数据这个0不可能出栈也就可以更加方便的计算宽度了。
情况二遍历完heights数组后栈中还留有有效数据部分柱形的最大矩形还未确定如下图 要计算出每个柱形的最大矩形也就是要将栈中的每个下标都出栈而要确保每个下标都可以出栈那就要保证进栈下标代表的高度要小于栈中元素对应的高度因此我们可以在heights数组的末尾再加上一个0这样就可以保证在遍历完heights数组的同时每个高度的最大矩形都可以被计算了。
这两个高度为0站在数组两边的柱形就是我们常说的哨兵
实现代码
int largestRectangleArea(int* heights, int heightsSize){//添加哨兵位heights (int*)realloc(heights, sizeof(int) * (heightsSize 2));heights[heightsSize 1] 0; //尾部添加0for (int i heightsSize; i 0; i--)heights[i] heights[i - 1];heights[0] 0; //头部添加0int *stack (int*)malloc(sizeof(int) * (heightsSize 2));int top 0;int ret_size 0;for (int i 0; i heightsSize 2; i){//当栈不为空并且进栈元素小于栈顶元素//就开始计算矩形面积while (top ! 0 heights[i] heights[stack[top - 1]]){//栈顶元素出栈int high_index stack[top - 1];top--;int wide i - stack[top - 1] - 1; //宽度int high heights[high_index]; //高度ret_size ret_size wide * high ? ret_size : wide * high;}//计算完成后或者没有进入循环进栈元素都要入栈stack[top] i;}free(stack); //释放栈return ret_size;
}
