題目

給定一個數(shù)組, 找出數(shù)組構(gòu)成的矩形面積.矩形的寬度就是數(shù)組兩個數(shù)的下標(biāo)的距離, 長度就是數(shù)組兩個數(shù)字的最小值.

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

思路1

時間復(fù)雜度O(n*n)

直接遍歷組合出所有情況, 效率非常低.

int maxArea(vector<int>& height) {

    int result = 0;
    for (int i = 0; i < height.size(); i++)
        for (int j = i + 1; j < height.size(); j++)
            result = max(result, min(height[i], height[j]) * (j - i));
    return result;
}

思路2

時間復(fù)雜度O(n)

設(shè)立兩個指針, 一個指向最左邊邊界, 一個指向最右邊邊界. 兩個指針都向?qū)Ψ揭苿? 每次都是較小的一邊移動.

int maxArea(vector<int>& height) {

    int result = 0;

    int l = 0, r = (int)height.size() -1;
    while (l < r) {
        int lHeight = height[l];
        int rHeight = height[r];
        result = max(result, min(height[l], height[r]) * (r-l));
        if (lHeight > rHeight) {
            r--;
        } else {
            l++;
        }
    }
    return result;
}

總結(jié)

同時向中間移動, 是一個比較難以理解的思路, 可以通過畫圖幫助理解.

抽象的數(shù)學(xué)問題通過畫圖可以幫助理解, 轉(zhuǎn)化為數(shù)學(xué)公式.