962-最大寬度坡

Ali_ 發(fā)布于2019-08-16 14:04 / 2346人閱讀

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

前言

Weekly Contest 116 的最大寬度坡：

給定一個整數(shù)數(shù)組 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

解題思路

本題中的元組個人感覺是一個煙霧彈，就算不了解元組的概念也能夠完成本題。本題的邏輯雖然不復(fù)雜，但是如果只是按照邏輯實現(xiàn)，會出現(xiàn)Time Limit Exceeded的情況，需要在實現(xiàn)的代碼上進行算法的優(yōu)化，減少循環(huán)次數(shù)從而避免 Time Limit Exceeded。

本題的邏輯實現(xiàn)其實很簡單，使用雙指針法即可完成。
首先第一個指針有序的遍歷每個元素，當(dāng)?shù)谝粋€指針指向一個元素時，第二個指針則遍歷這個元素后的每一個元素，并依次與第一個指針指向的元素進行比較，如果值比它小，則計算坡度并與當(dāng)前最大坡度進行比較，記錄較大值。

實現(xiàn)代碼 邏輯實現(xiàn)

這個代碼是根據(jù)題意實現(xiàn)的基礎(chǔ)代碼，會出現(xiàn)Time Limit Exceeded的情況

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

算法優(yōu)化

    /**
     * 962. 最大寬度坡
     * @param A
     * @return
     */
    public int maxWidthRamp(int[] A) {
        //最大寬度
        int maxWidth=0;
        //理論最大寬度
        int mayMaxWidth=0;
        for(int i=0;i=mayMaxWidth){//超過理論最大值表示已經(jīng)找到最大寬度坡，直接終止循環(huán)
                break;
            }
            for(int j=i+1;j=(j-i)?maxWidth:j-i;//計算最大寬度
                }
            }
        }
        return maxWidth;
    }