leetcode分类刷题：基于数组的双指针（四、小的移动）

leetcode上有些题是真的太难了，正常读题之后完全想不到要用双指针来求解，本次博客总结的题目是双指针初始时位于数组两端，哪个元素小就移动哪个指针

11. 盛最多水的容器

1、这道题放在42. 接雨水的相似题目里，可能是因为它们都有相似的双指针解法吗？从解题代码上看，可能本题的双指针更好理解一些
2、解题思路：左右指针从两侧同时遍历，哪个指针对应的元素小就更新哪个指针，等价于对应的面积可能变大；这个思路巧妙但不是那么好想

from typing import List
'''
11. 盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例 1:
    输入：[1,8,6,2,5,4,8,3,7]
    输出：49 
    解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
题眼：
思路：双指针：左右指针从两侧同时遍历，哪个指针对应的元素小就更新哪个指针，等价于对应的面积可能变大；这个思路巧妙但不是那么好想
'''


class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        result = min(height[left], height[right]) * (right - left)  # result初始值为处于数组边界情况的面积
        while left < right:
            if height[left] >= height[right]:  # 更新right才可能获得更大面积
                right -= 1
            elif height[left] < height[right]:  # 更新left才可能获得更大面积
                left += 1
            result = max(result, min(height[left], height[right]) * (right - left))
        return result


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            in_line = input().strip().split('=')
            height = [int(n) for n in in_line[1].strip()[1: -1].split(',')]
            print(obj.maxArea(height))
        except EOFError:
            break
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

42. 接雨水

1、下一个更大的数的变体题目，即左右两边下一个最大的数：这道题目最关键的地方在于理解题目，每个位置接雨水的量取决于左右两边的最大值，因此按照该思路定义两个数组，分别保存左右两边的最大值，然后再次遍历序列依次累计雨水量即可
2、这道题也可以按照单调栈的解法思路：按照“大小大”规律求夹着的面积，与栈的先入后出思想一致：小于栈顶元素入栈；等于栈顶元素则替换栈顶元素；大于栈顶元素则判断“大小大”计算面积，按照行为单位求雨水量
3、这道题还可以用双指针的解法思路：左右指针从两侧同时遍历，并分别维护左右两侧的最大值标记，哪个指针对应的元素小就更新哪个，等价于哪个指针可以根据两个最大值标记计算接水量，就移动哪个指针；这个思路巧妙但更难了，不是太常规

from typing import List
'''
42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
示例 1:
    输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
    输出：6
    解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
题眼：
思路1、模拟：每个位置接雨水的量取决于左右两边的最大值，因此，定义两个数组，分别保存左右两边的最大值（包括自己，闭区间考虑）；这种思路是按照列为单位求
雨水量的，简单直观，建议掌握！
思路2、单调栈：按照“大小大”规律求夹着的面积，与栈的先入后出思想一致：小于栈顶元素入栈；等于栈顶元素则替换栈顶元素；大于栈顶元素则判断“大小大”计算面积；
这种思路按照行为单位求雨水量的，这种解释不是太好理解，还不如按照括号配对的思路理解，按照这种思路有点难
思路3、双指针：左右指针从两侧同时遍历，并分别维护左右两侧的最大值标记，哪个指针对应的元素小就更新哪个，等价于哪个指针可以根据两个最大值标记计算接水量，
就移动哪个指针；这个思路巧妙但更难了，不是太常规，理解起来有点吃力
'''


class Solution:
    def trap(self, height: List[int]) -> int:
        # # 思路1、模拟：每个位置接雨水的量取决于左右两边的最大值，因此，定义两个数组，分别保存左右两边的最大值（包括自己，闭区间考虑）
        # lmax = [0] * len(height)
        # maxNum = 0
        # for i in range(len(height)):
        #     maxNum = max(maxNum, height[i])
        #     lmax[i] = maxNum
        # rmax = [0] * len(height)
        # maxNum = 0
        # for i in range(len(height) - 1, -1, -1):
        #     maxNum = max(maxNum, height[i])
        #     rmax[i] = maxNum
        # result = 0
        # for i in range(len(height)):
        #     result += min(lmax[i], rmax[i]) - height[i]
        # return result

        # # 思路2、单调栈：按照“大小大”规律求夹着的面积，与栈的先入后出思想一致：小于栈顶元素入栈；等于栈顶元素则替换栈顶元素；
        # # 大于栈顶元素则判断“大小大”计算面积
        # stk = []
        # result = 0
        # for i in range(len(height)):
        #     if len(stk) == 0:
        #         stk.append(i)
        #     else:
        #         if height[i] < height[stk[-1]]:
        #             stk.append(i)
        #         elif height[i] == height[stk[-1]]:  # 这一步可以注释掉，合并到上一步入栈
        #             stk.pop()
        #             stk.append(i)
        #         elif height[i] > height[stk[-1]]:
        #             while len(stk) > 0 and height[i] > height[stk[-1]]:
        #                 right = height[i]
        #                 mid = height[stk.pop()]
        #                 if len(stk) > 0:
        #                     left = height[stk[-1]]
        #                     result += (min(left, right) - mid) * (i - stk[-1] - 1)
        #             stk.append(i)
        # return result

        # 思路3、双指针：左右指针从两侧同时遍历，并分别维护左右两侧的最大值标记，哪个指针对应的元素小就更新哪个，等价于哪个指针可以根据两个最大值标
        # 记计算接水量，就移动哪个指针
        left, right = 0, len(height) - 1
        lMax, rMax = height[left], height[right]  # lMax标记了left位置的左侧最大值（包括left本身）；rMax标记了right位置的右侧最大值
        # （包括right本身）
        result = 0
        while left < right:  # left==right时，表示定位到了数组中的最大值处了，这里不用计算，肯定不能接水
            if height[left] <= height[right]:  # 情况1：height[left]刚好为lMax，必有lMax<=rMax；情况2：height[left]之前的某个数
                # 为lMax，那么当时left能更新的条件必然是lMax<=rMax；那么在left位置，必然有lMax<=left位置自己的右侧最大值（本来就比rMax大）
                # 所以，left指针可以记计算接水量
                result += lMax - height[left]  # 因为lMax包含了left位置，所以不用担心该计算小于0
                left += 1
                lMax = max(lMax, height[left])
            elif height[left] > height[right]:  # 情况1：height[right]刚好为rMax，必有lMax>rMax；情况2：height[right]之前的某个数
                # 为lMax，那么当时right能更新的条件必然是lMax>rMax；那么在right位置，必然有right位置自己的左侧最大值（本来就比lMax大）>rMax
                # 所以，right指针可以记计算接水量
                result += rMax - height[right]  # 因为rMax包含了right位置，所以不用担心该计算小于0
                right -= 1
                rMax = max(rMax, height[right])
        return result


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            in_line = input().strip().split('=')
            height = [int(n) for n in in_line[1].strip()[1: -1].split(',')]
            print(obj.trap(height))
        except EOFError:
            break
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90