962-最大寬度坡

Ali_ 發布于2019-08-16 14:04 / 2352人閱讀

摘要：前言的最大寬度坡給定一個整數數組，坡是元組，其中且。找出中的坡的最大寬度，如果不存在，返回。示例輸入輸出解釋最大寬度的坡為且示例輸入輸出解釋最大寬度的坡為且提示解題思路本題中的元組個人感覺是一個煙霧彈，就算不了解元組的概念也能夠完成本題。

前言

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;
    }

云服務器 GPU云服務器 html寬度最大高家坡專線定制租賃費用屏幕寬度適應寬度

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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