题解 | #接雨水问题#

解题思路：
1. 木桶的容量取决于最短木板，可能存在多个木桶
2. 寻找第i个桶，左边的木板
3. 寻找第i个桶，右边的木板
4. 计算木板之间的容量
5. 重复2-4， 直到数组结尾

#
# max water
# @param arr int整型一维数组 the array
# @return long长整型
#
class Solution:
    def _get_first(self, arr, start_i, end_i):
        """寻找作为桶的第一根木板"""
        for i in range(start_i, end_i):
            if arr[i] > arr[i+1]:
                return i
        return -1

    def _get_last(self, arr, first_i, start_i, end_i):
        """寻找作为木桶的最后一根木板"""

        # 找不到比首个木板最长的那个，就找[start_i+1, end_i] 的最大值对应的下标
        max_num_idx, max_num = -1, -1
        for i in range(start_i, end_i+1):
            if arr[i] >= arr[first_i]:
                return i

            if i > start_i and max_num < arr[i]:
                max_num = arr[i]
                max_num_idx = i
        return max_num_idx

    def maxWater(self , arr ):
        # write code here
        len_arr_idx = len(arr) - 1
        rnt = 0
        start_i = 0
        while True:
            first_i = self._get_first(arr, start_i, len_arr_idx)
            if first_i == -1 or first_i == len_arr_idx -1:
                break

            last_i = self._get_last(arr, first_i, first_i+1, len_arr_idx)
            # 选择最短木板作为木桶的容量
            min_num = min(arr[last_i], arr[first_i])
            for i in range(first_i+1, last_i):
                tmp = min_num - arr[i]
                if tmp > 0:
                    rnt += tmp

            if last_i == len_arr_idx:
                break
            start_i = last_i

        return rnt