​LeetCode刷題實戰11: 盛最多水的容器

2021-02-08 程序IT圈

算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！


今天和大家聊的問題叫做盛最多水的容器  ，我們先來看題面：

https://leetcode-cn.com/problems/container-with-most-water


Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.Note: You may not slant the container and n is at least 2.The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.


題意


給定n個非負整數，表示水庫當中隔板的高度。隔板之間的距離為1，當下要從n個隔板當中選出兩個，在其中注水，並且要使得容納的水儘量多。請問最多能容納多少水？可以忽略隔板的寬度，將水庫看成是正規的長方體。


樣例


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


題解


由於水庫可以看成是正規的長方體，所以水庫的體積可以簡化為橫截面積。也就是說我們要選擇兩個隔板，使得隔板之間圍成的矩形面積最大。


首先思考暴力求解，我們只需要枚舉矩形的兩邊，兩邊有了之後，矩形的長，也就是兩邊之間的距離，矩形的寬就是兩邊的較小值，所以複雜度是 O(n²) 。


這樣寫的代碼也很簡單，只有幾行：


for i in range(n):  for j in range(i+1, n):    ret = max(ret, (j-i) * min(a[i], a[j]))return ret

我們來思考怎麼優化，顯然大部分情況下 O(n²) 的算法往往都不是最優解。考慮一個很簡單的問題，為什麼取最左邊和最右邊的隔板不行呢？這樣不是矩形的長最長麼？

不行的原因很簡單，因為矩形的長雖然是最長，但是矩形的寬不一定很寬。有可能這樣的寬很短，就像上面圖中展示的一樣。如果這時候的結果不是最佳值，那麼最佳答案的矩形長一定小於n。如果我們用i和j指代最優解的左右兩邊的下標，那麼顯然有1 <= i < j <= n。

也就是說i,j 的位置應該在1, n的內部。我們可以想像一開始的時候i指向1，j指向n，然後逐漸移動到了最優解的位置。我們應該移動i和j，但是每次應該怎麼移動呢？究竟是移動i還是移動j呢？

其實稍微想一下就能想到答案，應該移動i和j兩個當中隔板比較短的那個。假設i的隔板長度小於j，即使移動i，導致碰到了更長的隔板，面積也不會變大，因為j的長度並沒有變，它依舊是短板。所以我們只有移動其中較短的那個，才有讓矩形面積變大的可能。

如果i和j的長度一樣怎麼辦？答案是隨便移動哪個都一樣，有些同學可能還有顧慮。我們不妨使用一下我們之前介紹貪心算法的時候提到的均等假設法。

我們來舉個例子，假設水庫隔板的情況是：

5 10 X .. X 4 5

我們一開始的時候i指向左邊的5，j指向右邊的5，這時候i和j相等。如果移動左邊的i，到10，面積並沒有變大。接下來會一直移動右邊的j，直到j遇到大於10的為止。並不會出現影響正確結果的情況。如果移動右邊的j呢？其實也是一樣的，因為如果j沒有遇到大於5的元素，無論左邊指向什麼地方，面積都不會增大。當j遇到5以上的數的時候，必然會移動左邊的i，一樣可能增大面積。

5 10 X .. X 11 5

我們再看這個例子，如果10和11圍成的結果是正確答案，那麼不論先移動i還是先移動j都是一樣的。本質上來說，如果矩形面積要增大，必須要i和j同時指向比當前更大的元素才行，所以先移動哪個並不會影響結果。

這樣一來，寫代碼就方便了，我們可以人為規定如果出現相等，就移動i。寫出來代碼如下：
i, j = 0, n-1
ret = 0
while i < j:
  ret = max(ret, (j - i) * min(a[i], a[j]))
  if a[i] <= a[j]:
    i += 1
  else:
    j -= 1
return ret

這道題既可以認為是貪心算法，也可以認為是兩指針維護區間的問題。不論怎麼樣解釋，寫出來的代碼是一樣的，我個人覺得還是很巧妙的，很適合初學者練手，並且難度也不是很大。希望大家都能領會。

今天的文章就到這裡，如果覺得有所收穫，請順手點個在看或者轉發吧，你們的支持是我最大的動力。

相關焦點

  • 盛最多水的容器 | Leetcode題解
    找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。**說明：**你不能傾斜容器。在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 49。思路 1（javascript）:題目中說找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。 ，因此符合直覺的解法就是固定兩個端點，計算可以承載的水量， 然後不斷更新最大值，最後返回最大值即可。
  • 【leetcode】11. Container With Most Water | 盛最多水的容器
    如果你看不懂英文，我給你提供了中文版的連結：https://leetcode-cn.com/problems/container-with-most-water/   還有，點擊閱讀原文可以進入leetcode原題示例Input: [1,8,6,2,5,4,8,3,7]Output: 4難度係數Medium
  • ​LeetCode刷題實戰42:接雨水
    所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做 接雨水，我們先來看題面：https://leetcode-cn.com/problems/trapping-rain-water/Given n non-negative integers representing an elevation map where the width of each bar
  • ​LeetCode刷題實戰139:單詞拆分
    所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做 單詞拆分，我們先來看題面：https://leetcode-cn.com/problems/word-break/Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be
  • 帶你狂刷算法Leetcode題!短時間內快速獲得實戰能力!
    但對於初學者來說，很容易沉迷在刷題的數量中，覺得如果能刷完這1000道題，自己一定能夠有所飛躍。但實際上，低效率的重複對你來說，根本就無法掌握到解題的精髓，一旦題目有所變動，就無法舉一反三。那究竟應該怎麼刷題才高效呢？
  • ​LeetCode刷題實戰79:單詞搜索
    所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做 單詞搜索，我們先來看題面：https://leetcode-cn.com/problems/word-search/Given a 2D board and a word, find if the word exists in the grid.
  • LeetCode刷題第三周【數組(簡單)】
    數組是目前Leetcode上題量最多的一個模塊了。刷題前我們來了解一下什麼是數組：數組是在程序設計中，為了處理方便， 把具有相同類型的若干元素按有序的形式組織起來的一種形式。首先，數組會利用 索引 來記錄每個元素在數組中的位置，且在大多數程式語言中，索引是從 0 算起的。我們可以根據數組中的索引，快速訪問數組中的元素。事實上，這裡的索引其實就是內存地址。
  • leetcode刷題指南之RussianDollEnvelopes
    問最多可以幾個套娃放在一起。 比如，[[5,4],[6,4],[6,7],[2,3]]的答案是３，因為[2,3] => [5,4] => [6,7]2.envelopes) 5{ 6    sort(envelopes.begin(),envelopes.end()); 7    int n=envelopes.size(); 8    if(n==0)    return 0; 9    int dp[n];10    for(int i=0;i<n;i++)    dp[i]=1;11
  • ​LeetCode刷題實戰91:解碼方法
    所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做 解碼方法，我們先來看題面：https://leetcode-cn.com/problems/decode-ways/A message containing letters from A-Z is being encoded to numbers using the following mapping
  • ​LeetCode刷題實戰15題: 三數之和
    所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做三數之和 ，我們先來看題面：https://leetcode.com/problems/3sum/描述給定一個整數的數組，要求尋找當中所有的a，b，c三個數的組合，使得三個數的和為0.注意，即使數組當中的數有重複，同一個數也只能使用一次。
  • ​LeetCode刷題實戰36: 有效的數獨
    所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做 有效的數獨，我們先來看題面：https://leetcode-cn.com/problems/valid-sudoku/Determine if a 9x9 Sudoku board is valid.
  • ​LeetCode刷題實戰198:打家劫舍
    所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做 打家劫舍，我們先來看題面：https://leetcode-cn.com/problems/house-robber/You are a professional robber planning to rob houses along a street.
  • ​LeetCode刷題實戰38: 外觀數列
    所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做 外觀數列，我們先來看題面：https://leetcode-cn.com/problems/count-and-say/Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.
  • ​LeetCode刷題實戰57:插入區間
    所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做 插入區間，我們先來看題面：https://leetcode-cn.com/problems/insert-interval/Given a set of non-overlapping intervals, insert a new interval into the intervals (merge
  • ​LeetCode刷題實戰179:最大數
    所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做 最大數  ，我們先來看題面：https://leetcode-cn.com/problems/largest-number/Given a list of non-negative integers nums, arrange them such that they form the largest number.
  • ​LeetCode刷題實戰70:爬樓梯
    所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做 爬樓梯，我們先來看題面：https://leetcode-cn.com/problems/climbing-stairs/You are climbing a stair case.
  • ​LeetCode刷題實戰134:加油站
    所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！https://leetcode-cn.com/problems/gas-station/There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
  • ​LeetCode刷題實戰93:復原IP位址
    所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做 復原IP位址，我們先來看題面：https://leetcode-cn.com/problems/restore-ip-addresses/Given a string s containing only digits, return all possible valid IP addresses that
  • 春節大禮包|刷題技巧+80道Leetcode
    為了跳槽，我前兩年的春節都是在刷題中度過的，目前為止刷了小四百道leetcode，也算是有一些經驗，今天就跟大家分享下學習方法和我總結的乾貨。後來發現了 Leetbook[1] 這個寶藏，才算是找到了適合自己的刷題方法。
  • ​LeetCode刷題實戰54:螺旋矩陣
    所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做 螺旋矩陣，我們先來看題面：https://leetcode-cn.com/problems/spiral-matrix/Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in