leetcode-11

11. Container With Most Water

Leetcode 11

I solved this problem using C++.
My idea: two for loops to iterate through the vector height and calculate the area of the container.

However, this solution is not efficient because it has a time complexity of O(n^2).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int maxArea(vector<int>& height) {
        int max_value = 0;
        for (int i = 0; i < height.size(); i++) {
            for (int j = i + 1; j < height.size(); j++) {
                int area = min(height[i], height[j]) * (j - i);
                max_value = max(max_value, area);
            }
        }
        return max_value;
    }
};

use two pointers

  1. set l to 0 and r to the size of the vector height - 1.
  2. use a while loop to iterate through the vector.
  3. set area to the minimum of height[l] and height[r] multiplied by r - l.
  4. move the pointer of the smaller height to the next position.
  5. return the maximum area.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxArea(vector<int> &height)
    {
        int max_value = 0;
        int left = 0, right = height.size() - 1;
        while (left < right) {
            int area = min(height[left], height[right]) * (right - left);
            max_value = max(max_value, area);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return max_value;
    }
};

Why move the pointer of the smaller height?

Because the area is determined by the smaller height, moving the pointer of the smaller height may lead to a larger area.
If we move the pointer of the larger height, the area will not change, but we may miss a larger area.

conclusion

Today’s Saturday early morning, and I drank a tin of beer just now😏
Maybe I should stop drinking beer and start go to bed earlier😥…