时间轴

2025-10-04

init

题目：

P11 盛水最多的容器

https://leetcode.cn/problems/container-with-most-water/description/?envType=daily-question&envId=2025-10-04

这题是经典的双指针题，但是我最开始的解法并未利用双指针，而是基于这样一个事实：
如果某一个端点构成容器的一侧，那么构成容器盛水最多的另一个端点是离它最远的且大于或等于它的高度的端点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <vector>

using std::vector;

class Solution {
public:
  int maxArea(vector<int> &height) {
    // 从height最小的开始，离当前的端点最远且大于等于height的(左右都要寻找)
    int n, i, j;
    int max = -1;
    int curr_height;
    n = height.size();

    for (i = 0; i < n; i++) {
      curr_height = height[i];
      for (j = n - 1; j > i; j--) {
        if (height[j] >= curr_height) {
          max = std::max(max, curr_height * (j - i));
          break;
        }
      }
      for (j = 0; j < i; j++) {
        if (height[j] >= curr_height) {
          max = std::max(max, curr_height * (i-j));
          break;
        }
      }
    }
    return max;
  }
};

上述解法虽然优化了暴力双循环，但最坏时间复杂度还是 O(n^2)还是不如双指针效率高：

  • 面积由 短板高度 × 宽度 决定。

    如果移动长板，宽度减少但高度不一定增加，所以面积不会变大。所以我们应该 始终移动短板指针，这样才有可能找到更大的面积。

时间复杂度 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <vector>
#include <algorithm>
using std::vector;

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int max_area = 0;

        while (left < right) {
            int h = std::min(height[left], height[right]);
            int w = right - left;
            max_area = std::max(max_area, h * w);

            // 移动短板
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return max_area;
    }
};