当前位置: 首页 > news >正文

网站主机安全湖州网站建设制作

网站主机安全,湖州网站建设制作,企业做电商网站有哪些内容,梅林网站建设(一)问题描述 84. 柱状图中最大的矩形 - 力扣(LeetCode)84. 柱状图中最大的矩形 - 给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。求在该柱状图中,能够勾…

(一)问题描述

84. 柱状图中最大的矩形 - 力扣(LeetCode)84. 柱状图中最大的矩形 - 给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。求在该柱状图中,能够勾勒出来的矩形的最大面积。 示例 1:[https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg]输入:heights = [2,1,5,6,2,3]输出:10解释:最大的矩形为图中红色区域,面积为 10示例 2:[https://assets.leetcode.com/uploads/2021/01/04/histogram-1.jpg]输入: heights = [2,4]输出: 4 提示: * 1 <= heights.length <=105 * 0 <= heights[i] <= 104https://leetcode.cn/problems/largest-rectangle-in-histogram/description/?envType=study-plan-v2&envId=top-100-liked

给定 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

(二)解决思路

        先说结论:对于一个柱子,它能构成的最大面积长方形的宽在它左侧高度最小柱子和右侧高度最小柱子之间(不包含左侧高度最小柱子和右侧高度最小柱子),高即柱子本身的高度。

        这里采用单调栈来计算各个柱子的左边界和右边界数组。以求左边界数组为例,当栈顶元素大于当前元素时就将栈顶元素弹出,并将当前柱子的位置加入栈中。这是因为如果当前柱子的高度更小,那么后面其他柱子的左边界肯定取当前柱子或者后面比当前柱子更矮的柱子,而不是栈顶柱子。

        我一开始想到了42. 接雨水这道题,但是这道题不用获取某个柱子和它相邻柱子之间的大小关系,某个柱子能接的水仅由它左侧或右侧中某一侧的最大高度有关,因此思路还是有所差别。

class Solution {public int largestRectangleArea(int[] heights) {int n=heights.length;Stack<Integer> st=new Stack<>();//求左边界int[] left=new int[n];for(int i=0;i<heights.length;i++){while(!st.isEmpty()&&heights[i]<=heights[st.peek()]){st.pop();}left[i]=(st.isEmpty()?-1:st.peek());st.push(i);}st.clear();//求右边界int[] right=new int[n];for(int i=n-1;i>=0;i--){while(!st.isEmpty()&&heights[i]<=heights[st.peek()]){st.pop();}right[i]=(st.isEmpty())?n:st.peek();st.push(i);}int ans=0;for(int i=0;i<n;i++){ans=Math.max(ans,(right[i]-left[i]-1)*heights[i]);}return ans;}
}
http://www.dinnco.com/news/35482.html

相关文章:

  • 怎么可以上传自己做的网站永久8x的最新域名
  • 我的网站突然打不开了国内网络推广渠道
  • 如何绑定网站域名百度搜索关键词排名优化
  • wordpress 自己写云南优化公司
  • 了解网站建设管理百度登录个人中心官网
  • 盐城网站建设招聘哔哩哔哩推广网站
  • 产品开发管理系统seo求职
  • 电商网站 建设北京搜索引擎优化
  • 日本配色的网站推荐中国营销网
  • 网站首页banner动态化seo整站优化技术培训
  • 制作网站规划书百度人工优化
  • dreamweaver是系统软件吗seo搜索优化公司
  • 秦皇岛网站搜索排名网络销售平台排名
  • 网站数据库是什么手游推广渠道和推广方式
  • 做网站的厉害还是黑网站的厉害百度影音在线电影
  • wordpress 微站今日国内新闻大事20条
  • 做设计一般用的素材网站是什么意思设计个人网站
  • 手机wap网站 源码seo网站优化知识
  • 长沙专业网站制作新闻热点大事件
  • 政府类wap网站建设方案国内优秀个人网站欣赏
  • 网站建设的电话回访长春网站开发公司
  • 毕业答辩问题怎么做的这个网站厦门网络推广
  • 网站建设大全网络营销与直播电商怎么样
  • 贵州做网站找谁上海知名seo公司
  • 设计师交流网站电子商务网站建设与维护
  • 兄弟网络(西安网站建设制作公司)短视频营销
  • 模板网站可以自己买空间吗吗seoheuni
  • 自己建网站卖鞋青岛谷歌推广
  • 上海做网站的公司官网技能培训网
  • 网站301在哪里做青岛seo建站