[LeetCode] 用更簡單的方式分析與解決 #11 Container With Most Water

幾乎所有解答不管中英文都在講兩邊指針移動的演算法，難道就沒有其他解法? 我今天就來用一個很簡單的分析讓原本會超時 (TLE) 的暴力解法可以被 Accepted。

最大的容器有什麼特徵?

每個測資都一定有一個最大的容器，假設我們最後找到最大的容器好了:

我就想了一下，左邊什麼情況不會發生?

左邊有機會有更高的牆嗎?

不會，不然你早就找到更好的解答了:

因為不管怎樣左邊一定會凸出去一塊綠色的部分，那我們一開始找到的根本不是最佳解。

所以如果你找到最大的容器，左右邊絕對都不會有更高的牆:

可是演算法怎麼設計?

對啦，我們知道左右邊不會有更高的牆，可是我們還是要把解答找出來啊！演算法怎辦?

我們知道暴力解就是把每個可能性都 try 過，就會有兩個 for loop 一左一右試試看每種面積，我們就可以這樣寫:

#include <algorithm>

class Solution {
 public:
  int maxArea(std::vector<int> height) {
    int maxArea = 0;
    for (int left = 0; left < height.size(); left++) {
      const int heightLeft = height.at(left);
      for (int right = height.size() - 1; right > left; right--) {
        const int heightRight = height.at(right);
        const int width = right - left;
        const int minHeight = std::min(heightLeft, heightRight);
        const int area = minHeight * width;
        maxArea = std::max(area, maxArea);
      }
    }
    return maxArea;
  }
};

只是我第二層的 index 是從右往左，但只是和一般的作法方向相反而已，每種可能性都還是會試過，所以沒差。

這丟上去當然會超時:

但還沒結束。我們就來想像一下兩個 indexes 的移動過程，如果移動到一半找到目前最大的容器，繼續碰到一根更短的牆他就不可能有更好的解:

根據我們一開始的結論，不管更短的牆找到多大的容器，我們現在的容器一定更大。所以碰到比目前更短的牆我們根本就不用理他。

找個 LeetCode 問題描述中的圖片當例子，從左往右就會把這些牆都略過:

從右往左的話:

這樣子我們只要把會 TLE 的暴力解稍微改一下，如果更短就跳過:

#include <algorithm>

class Solution {
 public:
  int maxArea(std::vector<int> &height) {
    int maxArea = 0;
    int prevHeightLeft = 0;
    for (int left = 0; left < height.size(); left++) {
      const int heightLeft = height.at(left);
      if (prevHeightLeft >= heightLeft) continue;

      int prevHeightRight = 0;
      for (int right = height.size() - 1; right > left; right--) {
        const int heightRight = height.at(right);
        if (heightRight <= prevHeightRight) continue;

        const int width = right - left;
        const int minHeight = std::min(heightLeft, heightRight);
        const int area = minHeight * width;
        maxArea = std::max(area, maxArea);
        prevHeightRight = heightRight;
      }
      prevHeightLeft = heightLeft;
    }
    return maxArea;
  }
};

至少可以加快一些時間:

就解完啦！

一樣是 O(n^2) 怎麼會比較快? 因為省略掉一些牆之後 n 的數量就下降了。

結語

雖然時間慢到爆炸，但至少我們有動腦分析與設計，而不是就把程式碼和演算法直接丟上來給人參考。

和任何事一樣，寫程式最好玩的是思考的過程，這大概也是面試時面試官會想要看的東西。

下一篇我用圖片的方式來解釋最常見的雙指針作法為何不會有問題。

GitHub

有興趣的話我把 Code 和投影片我都放在 GitHub 上了。