视频学习记录

https://www.bilibili.com/video/BV1Qg411q7ia

  • 最重要的一点，在于给出了双指针在过程中，左右分别什么时候才动。就拿“11. 盛最多水的容器”来说，如果取其中较高的那个指针向中间移动，宽度肯定减少，而高度就算下个值比现在大也不会增加，因为另一边更小。所以要动矮的那个，万一取到高得多大值就可以弥补宽度大缩小。

  • 至于接雨水，核心在于把计算接住的雨水转换成一列列上水的累计。这样就能通过前后缀分解计算一列列的水。

例题和课后作业代码记录

11. 盛最多水的容器

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def maxArea(self, height: List[int]) -> int:
        # 时间复杂度 n，相向遍历一次，空间复杂度 1，额外空间与变量大小无关
        l = 0
        r = len(height)-1
        ans = 0
        while l < r:
            cur = min(height[l], height[r]) * (r-l)
            if cur > ans:
                # print(l, r, cur, ans)
                ans = cur 
            
            if height[l] > height[r]:
                r -= 1
            else:
                l += 1
        return ans

42. 接雨水

https://leetcode.cn/problems/trapping-rain-water/description/

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution:
    def trap(self, height: List[int]) -> int:
        # 时间复杂度 n，相向遍历一次，空间复杂度 1，额外变量固定
        n = len(height)
        l = 0
        r = n-1
        ans = 0
        pre_max = 0
        suf_max = 0
        while l < r:
            pre_max = max(pre_max, height[l])
            suf_max = max(suf_max, height[r])

            if height[l] < height[r]:
                ans += pre_max-height[l]
                l += 1
            else:
                ans += suf_max-height[r]
                r -= 1
        return ans


        # 时间复杂度 n，空间复杂度 n，前后缀都存
        n = len(height)
        # 前后缀最大值
        front = [0] * n
        back = [0] * n

        front[0] = height[0]
        for i in range(1, n):
            if height[i] > front[i-1]:
                front[i] = height[i]
            else:
                front[i] = front[i-1]
        
        back[-1] = height[-1]
        for i in range(n-2, -1, -1):
            if height[i] > back[i+1]:
                back[i] = height[i]
            else:
                back[i] = back[i+1]
        
        ans = 0
        for i in range(1, n-1):
            ans += max(min(front[i-1], back[i+1]) - height[i], 0)
        return ans

125. 验证回文串

https://leetcode.cn/problems/valid-palindrome/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def isPalindrome(self, s: str) -> bool:
        # 时间复杂度 n，空间复杂度 1
        n = len(s)
        s = s.lower()
        # print(s)
        l = 0
        r = n-1
        vocab = [chr(i) for i in range(97, 123)] + [chr(i) for i in range(48, 58)]
        while l < r:
            while l < r and s[l] not in vocab:
                l += 1
            while l < r and s[r] not in vocab:
                r -= 1
            if s[l] != s[r]:
                return False
            else:
                l += 1
                r -= 1

        return True

2105. 给植物浇水 II

https://leetcode.cn/problems/watering-plants-ii/description/

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
32
33
class Solution:
    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:
        # 时间复杂度 n，空间复杂度1 
        cur_a = capacityA
        cur_b = capacityB
        l, r = 0, len(plants)-1
        ans = 0

        while l < r:
            if cur_a >= plants[l]:
                cur_a -= plants[l]
            else:
                ans += 1
                cur_a = capacityA - plants[l]
            l += 1

            if cur_b >= plants[r]:
                cur_b -= plants[r]
            else:
                ans += 1
                cur_b = capacityB - plants[r]
            r -= 1
        
        if l == r:
            # 这里是两边各来到了相同的最后一个
            if cur_b > cur_a:
                if cur_b < plants[l]:
                    ans += 1
            else:
                if cur_a < plants[l]:
                    ans += 1

        return ans