962-最大宽度坡

Ali_ 发布于2019-08-16 14:04 / 2238人阅读

摘要：前言的最大宽度坡给定一个整数数组，坡是元组，其中且。找出中的坡的最大宽度，如果不存在，返回。示例输入输出解释最大宽度的坡为且示例输入输出解释最大宽度的坡为且提示解题思路本题中的元组个人感觉是一个烟雾弹，就算不了解元组的概念也能够完成本题。

前言

Weekly Contest 116 的最大宽度坡：

给定一个整数数组 A，坡是元组 (i, j)，其中  i < j 且 A[i] <= A[j]。这样的坡的宽度为 j - i。
找出 A 中的坡的最大宽度，如果不存在，返回 0 。
示例1：
输入：[6,0,8,2,1,5]
输出：4
解释：
最大宽度的坡为 (i, j) = (1, 5): A[1] = 0 且 A[5] = 5.
示例2：
输入：[9,8,1,0,1,9,4,0,4,1]
输出：7
解释：
最大宽度的坡为 (i, j) = (2, 9): A[2] = 1 且 A[9] = 1.
提示：

2 <= A.length <= 50000
0 <= A[i] <= 50000

解题思路

本题中的元组个人感觉是一个烟雾弹，就算不了解元组的概念也能够完成本题。本题的逻辑虽然不复杂，但是如果只是按照逻辑实现，会出现Time Limit Exceeded的情况，需要在实现的代码上进行算法的优化，减少循环次数从而避免 Time Limit Exceeded。

本题的逻辑实现其实很简单，使用双指针法即可完成。
首先第一个指针有序的遍历每个元素，当第一个指针指向一个元素时，第二个指针则遍历这个元素后的每一个元素，并依次与第一个指针指向的元素进行比较，如果值比它小，则计算坡度并与当前最大坡度进行比较，记录较大值。

实现代码 逻辑实现

这个代码是根据题意实现的基础代码，会出现Time Limit Exceeded的情况

    public int maxWidthRamp(int[] A) {
        //最大宽度
        int maxWidth=0;
        for(int i=0;i=(j-i)?maxWidth:j-i;//计算最大宽度
                }
            }
        }
        return maxWidth;
    }

算法优化

    /**
     * 962. 最大宽度坡
     * @param A
     * @return
     */
    public int maxWidthRamp(int[] A) {
        //最大宽度
        int maxWidth=0;
        //理论最大宽度
        int mayMaxWidth=0;
        for(int i=0;i=mayMaxWidth){//超过理论最大值表示已经找到最大宽度坡，直接终止循环
                break;
            }
            for(int j=i+1;j=(j-i)?maxWidth:j-i;//计算最大宽度
                }
            }
        }
        return maxWidth;
    }

云服务器海外云主机 html宽度最大高家坡专线定制租赁费用屏幕宽度适应宽度

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72811.html

#yyds干货盘点# web安全day14：扫描与报破

摘要：干货盘点安全扫描与报破远程桌面可以发现这个设备被扫描出来，它就是我们的我们还可以尝试扫描它的操作系统。使用干货盘点安全扫描与报破远程桌面可以看到它运行的是或者或者，尽管不能完全一致，但是大致上为我们提供了准确的内容。 1、扫描技术扫描技术就是批量判断局域网中有哪些设备在线、这些设备的哪些服务开放。我们可以使用ping工具测...

番茄西红柿 2021-11-26 11:11 评论0 收藏2637
容器最大盛水量

摘要：容器最大盛水量给定个非负整数，，，，其中每个表示坐标，处的点。找到两条线，它们与轴一起形成一个容器，使得容器含有最多的水。容器最大盛水量 Container With Most Water 给定n个非负整数a1，a2，...，an，其中每个表示坐标（i，ai）处的点。绘制n条垂直线，使得线i的两个端点在（i，ai）和（i，0）处。找到两条线，它们与x轴一起形成一个容器，使得容器...

luckyw 2019-07-25 12:04 评论0 收藏0
Hugo入门详细教程

摘要：这是一种格式，前面的文章说过，支持三种格式，除了，还支持，方式。至于喜欢哪种格式，可以在中进行配置，默认使用的是格式。原文链接https://youendless.com/post/hugo_base/，主题https://github.com/kingfsen/Mainroad 首先访问Github下载Hugo的应用程序，Hugo各版本release文件下载地址https://github...

番茄西红柿 2019-04-23 11:42 评论0 收藏0
[聊一聊系列]聊一聊移动web分辨率的那些事儿

摘要：会各种折行，样式错乱，那么细致如苹果肯定不允许这种事情发生。又一次变迁苹果公司在年，推出了新一代的，他们的屏幕都比要宽要大。欢迎大家收看聊一聊系列，这一套系列文章，可以帮助前端工程师们了解前端的方方面面（不仅仅是代码）： https://segmentfault.com/blog/frontenddriver 不同于PC时代，移动web的样式更加多样，也由于手机分辨率的碎片化，移动w...

vibiu 2019-08-29 10:58 评论0 收藏0
小程序rich-text对富文本支持方案

摘要：小程序富文本解析目前小程序使用比较多的富文本方案一个是小程序自带的组件，一个是。使用方法文殊林舍山房由丽江铂尔曼度假酒店余明金老师设计，是丽江古城的网红民宿，年被评为全国家最美民宿，以及年最值得睡的张床。小程序富文本解析目前小程序使用比较多的富文本方案一个是小程序自带的rich-text组件，一个是wxPrase。 wxPrase原理是把原有的html标签全部解析成小程序的组件，这...

William_Sang 2019-08-29 17:21 评论0 收藏0