兩個直方圖之間的最大水量是多少？

-3

我最近碰到這個問題就來了：中n兩個直方圖之間的最大水量是多少？

您將得到高度直方圖每個寬1。你必須選擇任意兩個柱狀圖等，如果它開始下雨，所有其他直方圖（除了你們兩個已選擇）被移除，那麼在兩個直方圖之間收集的水被最大化。

Input: 9 3 2 5 9 7 8 1 4 6 Output: 25 在第三個和最後一個直方圖之間。

這是Trapping rain water問題的一個變種。

我嘗試了兩種解決方案，但都具有N^2的最壞情況複雜度。我們如何進一步優化。

Sol1：每對的蠻力。

int maxWaterCollected(vector<int> hist, int n) { 
    int ans = 0; 
    for (int i= 0; i < n; i++) { 
     for (int j = i + 1; j < n; j++) { 
      ans = max(ans, min(hist[i], hist[j]) * (j - i - 1)); 
     } 
    } 

    return ans; 
}

Sol2：保持一系列直方圖的高度順序。對於每個直方圖，在這個序列中找到最佳的直方圖。現在，如果所有的直方圖都是遞增的，那麼這個解決方案也會變成N^2。

int maxWaterCollected(vector<int> hist, int n) { 
    vector< pair<int, int> > increasingSeq(1, make_pair(hist[0], 0)); // initialised with 1st element. 
    int ans = 0; 
    for (int i = 1; i < n; i++) { 
     // compute best result from current increasing sequence 
     for (int j = 0; j < increasingSeq.size(); j++) { 
      ans = max(ans, min(hist[i], increasingSeq[j].first) * (i - increasingSeq[j].second - 1)); 
     } 

     // add this histogram to sequence 
     if (hist[i] > increasingSeq.back().first) { 
      increasingSeq.push_back(make_pair(hist[i], i)); 
     } 
    } 

    return ans; 
}

來源

2017-02-10 Atul Vaibhav

我已經提到過我的兩個方法，第一個是蠻力另一個是保持直方圖的遞增子的，但我覺得這個問題可以在更好的時間複雜度來解決。 –

[C++]觀衆傾向於將這些問題降低爲「缺乏努力」。 –

我在這裏沒有看到任何努力。「我嘗試了兩種解決方案」，但沒有發佈任何代碼？請，如果你嘗試，**添加你所做的代碼**。 – tadman

Jarod42看法是正確的，但它是從他簡短交不清楚爲什麼他的算法，在Python下面描述，正確的是：

def candidates(hist): 
    l = 0 
    r = len(hist) - 1 
    while l < r: 
     yield (r - l - 1) * min(hist[l], hist[r]) 
     if hist[l] <= hist[r]: 
      l += 1 
     else: 
      r -= 1 


def maxwater(hist): 
    return max(candidates(hist))

正確性的證明是通過歸納：最佳的解決方案是（1 ）屬於到目前爲止產生的候選人或（2）在[l, r]內選擇直方圖。基本情況很簡單，因爲所有直方圖都在[0, len(hist) - 1]之內。

感應式地，假設我們即將推進l或r。這些案例是對稱的，所以我們假設我們即將推進l。我們知道hist[l] <= hist[r]，所以價值是(r - l - 1) * hist[l]。鑑於任何其他正確的端點r1 < r，值爲(r1 - l - 1) * min(hist[l], hist[r1])，這是因爲r - l - 1 > r1 - l - 1和hist[l] >= min(hist[l], hist[r1])。我們可以排除所有這些解決方案不理想，所以提前l是安全的。

來源

2017-02-10 18:09:46

使用2個迭代器，一個從begin()，一個來自end() - 1。

直到2迭代是相等的：
比較當前結果與最大，並保持最大
移動迭代器具有較小的值（開始 - >端或端 - >開始）

複雜度：O(n)。

來源

2017-02-10 08:28:49 Jarod42

兩個直方圖之間的最大水量是多少？

回答

相關問題