2

n 個の負でない整数 a1、a2、...、an が与えられ、それぞれが座標 (i、ai) の点を表します。線 i の 2 つの端点が (i, ai) と (i, 0) になるように、n 本の垂直線が描かれます。x 軸と共にコンテナーを形成する 2 つの線を見つけて、コンテナーに最も多くの水が含まれるようにします。

注：容器を傾けないでください。

解決策の 1 つは、すべての線を取り、すべての線で領域を見つけることです。これには O(n^2) かかります。時間効率が悪い。

別の解決策として、DP を使用してすべてのインデックスの最大領域を見つけ、インデックス n で最大領域を取得することができます。O(n)だと思います。

もっと良い解決策はありますか？

4

7 に答える 7

3 
int maxArea(vector<int> &height) {
    int ret = 0;
    int left = 0, right = height.size() - 1;
    while (left < right) {
        ret = max(ret, (right - left) * min(height[left], height[right]));
        if (height[left] <= height[right])
            left++;
        else
            right--;
    }
    return ret;
}
于 2013-01-27T20:54:40.460 に答える
2

ここにいる多くの人は、この問題を最大四角形の問題と誤解していますが、そうではありません。

解決

  1. ai >= aj =< ak および i > j < k となるすべての要素 aj を削除します。これは線形時間で実行できます。
    1. 最大値午前を見つける
    2. = a1とする
    3. j = 2 ～ m-1 の場合、>= aj の場合は aj を削除、そうでない場合は = aj
    4. = とする
    5. j = n-1 から m+1 の場合、>= aj の場合は aj を削除し、そうでない場合は = aj の場合
  2. 結果の値がピラミッドのように見えることに注意してください。つまり、最大値の左側にあるすべての要素が厳密に増加し、右側にあるすべての要素が厳密に減少しています。
  3. i=1、j=n。m は最大の位置です。
  4. i<=m かつ j>=m の間
    1. ai と aj の間の領域を見つけ、最大値を追跡します
    2. ai < aj の場合、i+=1、そうでない場合は j-=1

複雑さは線形 (O(n))

于 2012-05-20T16:09:35.840 に答える
1

Java を使用した実装は次のとおりです。

基本的な考え方は、前後から2つのポインターを使用し、途中で面積を計算することです。

public int maxArea(int[] height) {
    int i = 0, j = height.length-1;
    int max = Integer.MIN_VALUE;

    while(i < j){
        int area = (j-i) * Math.min(height[i], height[j]);
        max = Math.max(max, area);
        if(height[i] < height[j]){
            i++;
        }else{
            j--;
        }
    }

    return max;
}
于 2013-11-03T20:39:41.520 に答える
0

この問題は線形時間で解くことができます。

  1. 考えられる左の壁 (位置と高さのペア) のリストを、高いものから低いものの順に作成します。これは、最も左にある可能性のある壁を取得してリストに追加し、可能なすべての壁を左から右に調べ、最後にリストに追加された壁よりも大きいすべての壁を取得することによって行われます。たとえば、配列の場合

    2 5 4 7 3 6 2 1 3

    考えられる左の壁は次のようになります (ペアは (pos, val)):

    (3, 7) (1, 5) (0, 2)

  2. 同じ方法で可能な右壁のリストを作成しますが、右から左に進みます。上記の配列の場合、考えられる右の壁は次のようになります。

    (3, 7) (5, 6) (8, 3)

  3. 2 つのリストの前にある壁の高さの最小値である、できるだけ高い水位から始めます。これらの壁を使用して水の総量を計算し (マイナスまたはゼロの場合もありますが、それで問題ありません)、リストの 1 つから要素をポップして水位を下げ、水位の低下が最も少なくなるようにします。これらの高さのそれぞれで可能な水量を計算し、最大値を取ります。

これらのリストでこのアルゴリズムを実行すると、次のようになります。

L: (3, 7) (1, 5) (0, 2)  # if we pop this one then our water level drops to 5
R: (3, 7) (5, 6) (8, 3)  # so we pop this one since it will only drop to 6
Height = 7
Volume = (3 - 3) * 7 = 0
Max = 0

L: (3, 7) (1, 5) (0, 2)  # we pop this one now so our water level drops to 5
R: (5, 6) (8, 3)         # instead of 3, like if we popped this one
Height = 6
Volume = (5 - 3) * 6 = 12
Max = 12

L: (1, 5) (0, 2)
R: (5, 6) (8, 3)
Height = 5
Volume = (5 - 1) * 5 = 20
Max = 20


L: (1, 5) (0, 2)
R: (8, 3)
Height = 3
Volume = (8 - 1) * 3 = 21
Max = 21

L: (0, 2)
R: (8, 3)
Height = 2
Volume = (8 - 0) * 2 = 16
Max = 21

ステップ 1、2、および 3 はすべて線形時間で実行されるため、完全な解にも線形時間がかかります。

于 2012-05-20T21:32:12.457 に答える
0

最良の答えはBlack_Riderによるものですが、説明はありませんでした。

このブログで非常に明確な説明を見つけました。簡単に説明すると、次のようになります。

長さ n の配列の高さを指定すると、次のようになります。

  1. できる限り幅の広いコンテナから始めます。つまり、左側の 0 から右側の n-1 までです。

  2. より良いコンテナが存在する場合、そのコンテナはより狭くなるため、その両側は現在選択されている下側よりも高くなければなりません。

  3. したがって、height[left] < height[right] の場合は left を (left+1) に変更し、そうでない場合は right を (right-1) に変更します。

  4. 新しい面積を計算し、これまでよりも優れている場合は交換します。

  5. 左 < 右の場合、2 からやり直します。

C++ での私の実装:

int maxArea(vector<int>& height) {
    auto current = make_pair(0, height.size() - 1);
    auto bestArea = area(height, current);

    while (current.first < current.second) {
        current = height[current.first] < height[current.second]
            ? make_pair(current.first + 1, current.second)
            : make_pair(current.first, current.second - 1);

        auto nextArea = area(height, current);
        bestArea = max(bestArea, nextArea);
    }

    return bestArea;
}

inline int area(const vector<int>& height, const pair<int, int>& p) {
    return (p.second - p.first) * min(height[p.first], height[p.second]);
}
于 2016-10-17T12:06:30.163 に答える
-1

この問題は、最大長方形問題の単純なバージョンです。与えられた状況は、バイナリ マトリックスとして表示できます。行列の行を X 軸、列を Y 軸と見なします。配列内のすべての要素 a[i] に対して、設定

Matrix[i][0] = Matrix[i][1] = ..... = Matrix[i][a[i]] = 1

たとえば - の場合a[] = { 5, 3, 7, 1}、バイナリ行列は次のように与えられます。

1111100
1110000
1111111
1000000
于 2012-05-20T14:40:36.293 に答える