前言

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.

提示：

1. 2 <= A.length <= 50000
2. 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<A.length-1;i++){for(int j=i+1;j<A.length;j++){if(A[i]<=A[j]){//比較兩個指針指向的元素值，滿足A[i] <= A[j]則計算寬度maxWidth=maxWidth>=(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<A.length-1;i++){//每次循環時，理論最大寬度應該不會超過數組最后一個元素的索引減去當前元素索引mayMaxWidth=A.length-1-i;if(maxWidth>=mayMaxWidth){//超過理論最大值表示已經找到最大寬度坡，直接終止循環break;}for(int j=i+1;j<A.length;j++){if(A[i]<=A[j]){//比較兩個指針指向的元素值，滿足A[i] <= A[j]則計算寬度maxWidth=maxWidth>=(j-i)?maxWidth:j-i;//計算最大寬度}}}return maxWidth;}