首页 > 编程语言 >算法学习day60单调栈part03-84

算法学习day60单调栈part03-84

时间:2023-06-16 23:13:36浏览次数:48  
标签:int part03 heights day60 length minRightIndex result minLeftIndex 84

package LeetCode.stackpart03;
/**
 * 84. 柱状图中最大的矩形
 * */
public class LargestRectangleHistogram_84 {
    public int largestRectangleArea(int[] heights) {
        int length = heights.length;
        int[] minLeftIndex = new int [length];
        int[] minRightIndex = new int [length];
        // 记录左边第一个小于该柱子的下标
        minLeftIndex[0] = -1 ;
        for (int i = 1; i < length; i++) {
            int t = i - 1;
            // 这里不是用if,而是不断向右寻找的过程
            while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];
            minLeftIndex[i] = t;
        }
        // 记录每个柱子右边第一个小于该柱子的下标
        minRightIndex[length - 1] = length;
        for (int i = length - 2; i >= 0; i--) {
            int t = i + 1;
            while(t < length && heights[t] >= heights[i]) t = minRightIndex[t];
            minRightIndex[i] = t;
        }
        // 求和
        int result = 0;
        for (int i = 0; i < length; i++) {
            int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);
            result = Math.max(sum, result);
        }
        return result;
    }
}

 

标签:int,part03,heights,day60,length,minRightIndex,result,minLeftIndex,84
From: https://www.cnblogs.com/lipinbigdata/p/17486655.html

相关文章

  • CodeForces 1841C Ranom Numbers
    洛谷传送门CF传送门先反转\(s\)串,然后考虑dp,设\(f_{i,j,0/1}\)为考虑了\([1,i]\),前缀最大值为\(j\),是否修改过字符的最大得分。转移讨论是否在这个位置修改即可。时间复杂度\(O(n)\)。code//Problem:C.RanomNumbers//Contest:Codeforces-Educational......
  • arcgis CGCS2000转GCS_WGS_1984坐标系
    第一步:生成坐标系转换文件方法:ArcToolbox——数据管理工具——投影和变换——创建自定义地理(坐标)变换确定之后,生成名为GCS_WGS_1984—CGCS2000的转换文件。第二步:生成坐标系转换文件方法:ArcToolbox——>数据管理工具——>投影和变换——要素(arcgis10.8已取消要素这一环)——......
  • 【843】dataframe相关操作
    按照列排序:pandas.DataFrame.sort_values创建dataframe:pandas读取字典(dict)数据 ......
  • 【841】shapely合并多个Polygon/MultiPolygon
    参考:Convertinglistofpolygonstomultipolygonusingshapely?MultiPolygon->Polygonlistlist(multiPoly.geoms)Polygonlist->MultiPolygonshapely.geometry.MultiPolygon([poly1,poly2,poly3,poly4,poly5]) ......
  • 84. 柱状图中最大的矩形
    给定n个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为1。求在该柱状图中,能够勾勒出来的矩形的最大面积。示例1:输入:heights=[2,1,5,6,2,3]输出:10解释:最大的矩形为图中红色区域,面积为10首先单调栈首先要确定左右的范围因为画矩形时,要找到......
  • 84 局部变量 在get set等方法中 ;成员变量在属性中
    packagecom.fqs.demo061302;publicclassGirl{//属性//成员变量Stringname;privateintage;publicvoidsetAge(intage){//【局部变量】名称可以和上面的【成员变量】一样//赋值if(age<50&&age>18){this......
  • 成功解决错误 CS8400 功能“创建目标类型对象”在 C# 8.0 中不可用。请使用语言版本 9
    成功解决错误CS8400功能“创建目标类型对象”在C#8.0中不可用。请使用语言版本9.0或更高版本。https://blog.csdn.net/RoseJFrame/article/details/129855616在使用ScottPlot例程中MultipleHistograms图表代码时遇到的问题错误CS8400功能“创建目标类型对象”在......
  • AtCoder Beginner Contest 284 ABCDE
    AtCoderBeginnerContest284A-SequenceofStringsProblemStatement题意:给你n个字符串,让你倒序输出Solve#include<bits/stdc++.h>usingnamespacestd;constintN=20;strings[N];intmain(){ intn; cin>>n; for(inti=1;i<=n;i++) cin>>s......
  • git问题:remote: [session-584b73b2] Access denied... The requ ested URL returned e
     error403是服务器拒绝了终端的访问,是账户密码的问题,是因为git客户端缓存了错误的密码。我是原来有个git账户,使用https方式,密码永久保存的方式,在操作另一个git账户时可能更新了缓存密码。方法:使用gitclonehttp://username:[email protected]/name/projectname.git克隆任......
  • hdu2084数塔(DP)
    思路:简单的数塔DP#include<stdio.h>#include<string.h>#include<algorithm>usingnamespacestd;inta[105][105],dp[105][105];intmain(){intt,n,i,j;scanf("%d",&t);while(t--){scanf("%d",......