[算法刷题]盛最多水的容器

Problem: 11. 盛最多水的容器

思路

刚开始只想着暴力，想法和现有的字符串中的最长回文串的思想差不多，定位一个字符串的start和end标志。
但是提交了一下发现超时了，主要还是限制条件比较难写，因此优化的话还是考虑双指针来做。

解题方法

在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽 底边宽度 −1-1−1​ 变短：
若向内 移动短板 ，水槽的短板 min(h[i],h[j])min(h[i], h[j])min(h[i],h[j]) 可能变大，因此下个水槽的面积 可能增大 。
若向内 移动长板 ，水槽的短板 min(h[i],h[j])min(h[i], h[j])min(h[i],h[j])​ 不变或变小，因此下个水槽的面积 一定变小 。
因此，初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。

复杂度

• 时间复杂度:

添加时间复杂度, 示例： $O(N)$

• 空间复杂度:

添加空间复杂度, 示例： $O(1)$

Code

class Solution:
    def maxArea(self, height: List[int]) -> int:
        start = 0 
        end = len(height) - 1
        res = 0

        while start < end:
            if height[start] < height[end]:
                res = max(res,height[start] * (end-start))
                start = start + 1
            else:
                res = max(res,height[end] * (end-start))
                end = end - 1
        return res 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

但刚开始的时候提交的是和字符串中最长回文串的思路去做的，一直报超时，但是实现起来也不是很难。

Code （无优化）

	class Solution:
    def maxArea(self, height: List[int]) -> int:
        max_vol = 0
        flag_start = 0

        start_index = 0
        while start_index < len(height):
            if height[start_index] < height[flag_start]:
                pass
            else:
                for i in range(start_index+1,len(height))[::-1]:
                    wid_ = i - start_index
                    hei_ = min(height[i],height[start_index])
                    vol = wid_ * hei_
                    if vol > max_vol:
                        max_vol = vol
                        flag_start = start_index

            start_index = start_index + 1
        return max_vol

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21