给定一个数组heights,长度为n,height[i]是在第i点的高度,那么height[i]表示的直方图,能够形成的最大矩形是多少? 1.每个直方图 宽度都为1 2.直方图 都是相邻的 3.如果不能形成矩形,返回0即可 4.保证返回的结果不会超过231-1 数据范围: 如输入[3,4,7,8,1,2],那么如下:-笔试面试资料

这是qklbishe.com第19423 篇笔试面试资料
提供答案分析,通过本文《给定一个数组heights,长度为n,height[i]是在第i点的高度,那么height[i]表示的直方图,能够形成的最大矩形是多少? 1.每个直方图 宽度都为1 2.直方图 都是相邻的 3.如果不能形成矩形,返回0即可 4.保证返回的结果不会超过231-1
数据范围:

如输入[3,4,7,8,1,2],那么如下:-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

给定一个数组heights,长度为n,height[i]是在第i点的高度,那么height[i]表示的直方图,能够形成的最大矩形是多少?
1.每个直方图宽度都为1
2.直方图都是相邻的
3.如果不能形成矩形,返回0即可
4.保证返回的结果不会超过231-1
数据范围:
给定一个数组heights,长度为n,height[i]是在第i点的高度,那么height[i]表示的直方图,能够形成的最大矩形是多少?      1.每个直方图 宽度都为1    2.直方图 都是相邻的    3.如果不能形成矩形,返回0即可    4.保证返回的结果不会超过231-1          数据范围:                      如输入[3,4,7,8,1,2],那么如下:
给定一个数组heights,长度为n,height[i]是在第i点的高度,那么height[i]表示的直方图,能够形成的最大矩形是多少?      1.每个直方图 宽度都为1    2.直方图 都是相邻的    3.如果不能形成矩形,返回0即可    4.保证返回的结果不会超过231-1          数据范围:                      如输入[3,4,7,8,1,2],那么如下:
如输入[3,4,7,8,1,2],那么如下:
给定一个数组heights,长度为n,height[i]是在第i点的高度,那么height[i]表示的直方图,能够形成的最大矩形是多少?      1.每个直方图 宽度都为1    2.直方图 都是相邻的    3.如果不能形成矩形,返回0即可    4.保证返回的结果不会超过231-1          数据范围:                      如输入[3,4,7,8,1,2],那么如下:
Java

给定一个数组heights,长度为n,height[i]是在第i点的高度,那么height[i]表示的直方图,能够形成的最大矩形是多少?      1.每个直方图 宽度都为1    2.直方图 都是相邻的    3.如果不能形成矩形,返回0即可    4.保证返回的结果不会超过231-1          数据范围:                      如输入[3,4,7,8,1,2],那么如下: 零葬

单调栈求解,遍历高度数组,在此过程中维持栈底到栈顶的单调递增,当遍历到某个位置i时:
  1. 如果栈为空或heights[i]>heights[stack.peek()],说明此时能保证单调性,直接把下标i压栈;
  2. 否则开始结算面积:先弹出栈顶元素,以heights[stack.pop()]作为高度,而此时i是它右边第一个比它小的高度,说明这个高度的矩形能够往右延展至i,让这个矩形从栈顶(矩形左边界)的位置延展至i,结算面积即可;不断弹栈,直到heights[i]压栈后可以保证栈的单调性,然后把i压栈,在弹栈的过程中不断更新矩形的左边界和矩形面积。

需要注意的是:遍历完数组后栈并不一定为空,所以还需要结算以栈中元素为矩形左边界构成的矩形面积(此时右边界为heights.length)。

import java.util.*;   public class Solution {     /**      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可      *      *       * @param heights int整型一维数组       * @return int整型      */     public int largestRectangleArea (int[] heights) {         // write code here         Stack<Integer> stack = new Stack<>();         int maxArea = 0;         for(int i = 0; i < heights.length; i++){             while(!stack.isEmpty() && heights[stack.peek()] > heights[i]){                 int h = heights[stack.pop()];                 int L = stack.isEmpty()? 0: stack.peek() + 1;                 maxArea = Math.max(maxArea, (i - L) * h);             }             stack.push(i);         }         while(!stack.isEmpty()){             int h = heights[stack.pop()];             int L = stack.isEmpty()? 0: stack.peek() + 1;             maxArea = Math.max(maxArea, (heights.length - L) * h);         }         return maxArea;     } }

可能有些新手会有这样的疑问:为什么单调栈求解题目的时候都是把下标压入栈中,而不是直接压数组元素?这是因为,题目给你的数组已经摊在这了,只要有下标,一定可以定位到某个高度。而如果你压入的是高度,在结算矩形面积的时候就难以确定矩形的底边是从哪到哪,因此压入下标所维持的信息是更多的。

今天 11:44:32 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 给定一个数组heights,长度为n,height[i]是在第i点的高度,那么height[i]表示的直方图,能够形成的最大矩形是多少? 1.每个直方图 宽度都为1 2.直方图 都是相邻的 3.如果不能形成矩形,返回0即可 4.保证返回的结果不会超过231-1 数据范围: 如输入[3,4,7,8,1,2],那么如下:-笔试面试资料

提供最优质的资源集合

立即查看 了解详情