Leetcode 42

Method 1: Dynamic Programming

For index i, the maximum height water can reach after raining is equal to the minimum of the maximum heights on both sides of index i. The amount of rainwater that can be collected at index i is equal to the maximum height water can reach at index i minus height[i].

A naive approach is to scan left and right for each element in the height array, recording the maximum height on both sides, and then calculate the rainwater that can be collected at each index position. Suppose the length of the height array is n. This approach requires O(n) time to scan both directions for each index position, so the total time complexity is O(n^2).

The high time complexity of the above method is because it requires scanning both directions for each index position. If we already know the maximum height on both sides of each position, we can calculate the total amount of rainwater that can be collected in O(n) time. Using dynamic programming, we can preprocess and find the maximum height on both sides of each position in O(n) time.

Create two arrays of length n, leftMax and rightMax. For 0 ≤ i < n, leftMax[i] represents the maximum height of height to the left of index i, and rightMax[i] represents the maximum height of height to the right of index i.

Obviously, leftMax[0] = height[0], and rightMax[n-1] = height[n-1]. The remaining elements of the two arrays are calculated as follows:

For 1 ≤ i ≤ n-1, leftMax[i] = max(leftMax[i-1], height[i]); For 0 ≤ i ≤ n-2, rightMax[i] = max(rightMax[i+1], height[i]).

Thus, we can iterate forward through the height array to get the value of each element in leftMax, and iterate backward through the height array to get the value of each element in rightMax.

After obtaining the values of each element in leftMax and rightMax, for 0 ≤ i < n, the rainwater that can be collected at index i is equal to min(leftMax[i], rightMax[i]) - height[i]. Iterate through each index position to get the total amount of rainwater that can be collected.

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        
        n = len(height)
        leftMax = [height[0]] + [0] * (n - 1)
        for i in range(1, n):
            leftMax[i] = max(leftMax[i - 1], height[i])

        rightMax = [0] * (n - 1) + [height[n - 1]]
        for i in range(n - 2, -1, -1):
            rightMax[i] = max(rightMax[i + 1], height[i])

        ans = sum(min(leftMax[i], rightMax[i]) - height[i] for i in range(n))
        return ans

Method 2: Monotonic Stack

In addition to calculating and storing the maximum height on both sides of each position, the total amount of rainwater that can be collected can also be calculated using a monotonic stack.

Maintain a monotonic stack, which stores indices such that the elements of the array height corresponding to these indices are in decreasing order from the bottom to the top of the stack.

Iterate through the array from left to right. When iterating to index i, if there are at least two elements in the stack, let the top element of the stack be top, and the element below top be left, then we have height[left] >= height[top]. If height[i] > height[top], then a region that can collect rainwater is found. The width of this region is i - left - 1, and the height is min(height[left], height[i]) - height[top]. The volume of rainwater that can be collected in this region can be calculated based on its width and height.

To find left, top must be popped from the stack. After calculating the rainwater that can be collected at top, left becomes the new top, and the above operation is repeated until the stack is empty, or the element of height corresponding to the index at the top of the stack is greater than or equal to height[i].

After calculating the rainwater that can be collected at index i, push i into the stack and continue to iterate over the following indices, calculating the rainwater that can be collected. After the iteration is complete, the total amount of rainwater that can be collected can be determined.

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        stack = list()
        n = len(height)
        
        for i, h in enumerate(height):
            while stack and h > height[stack[-1]]:
                top = stack.pop()
                if not stack:
                    break
                left = stack[-1]
                currWidth = i - left - 1
                currHeight = min(height[left], height[i]) - height[top]
                ans += currWidth * currHeight
            stack.append(i)
        
        return ans

Method 3: Two Pointers

In the dynamic programming approach, we need to maintain two arrays, leftMax and rightMax, thus the space complexity is O(n). Can we reduce the space complexity to O(1)?

Notice that the amount of rainwater that can be collected at index i is determined by the minimum of leftMax[i] and rightMax[i]. Since the array leftMax is computed from left to right and rightMax from right to left, we can use two pointers and two variables instead of two arrays.

Maintain two pointers left and right, and two variables leftMax and rightMax, initially left = 0, right = n - 1, leftMax = 0, rightMax = 0. The pointer left only moves to the right, and the pointer right only moves to the left. During the movement of the pointers, maintain the values of leftMax and rightMax.

While the two pointers have not met, perform the following operations:

• Update the values of leftMax and rightMax using the values of height[left] and height[right];
• If height[left] < height[right], then leftMax < rightMax. The amount of rainwater that can be collected at index left is leftMax - height[left]. Add the amount of rainwater that can be collected at index left to the total amount, and then move left to the right by one position;
• If height[left] >= height[right], then leftMax >= rightMax. The amount of rainwater that can be collected at index right is rightMax - height[right]. Add the amount of rainwater that can be collected at index right to the total amount, and then move right to the left by one position.

When the two pointers meet, the total amount of rainwater that can be collected is obtained.

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        left, right = 0, len(height) - 1
        leftMax = rightMax = 0

        while left < right:
            leftMax = max(leftMax, height[left])
            rightMax = max(rightMax, height[right])
            if height[left] < height[right]:
                ans += leftMax - height[left]
                left += 1
            else:
                ans += rightMax - height[right]
                right -= 1
        
        return ans