Monotonic Queue

Monotonic Queue realated problems are hard. It is even harder than DP and Graph problems. Once you know how to solve these problems, you will enjoy another level of elegant coding. — jimmy shen, 2020

Let’s explore this topic through several examples.

42. Trapping Rain Water

Solution 1

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height)<=2:return 0
        left = [height[0]]
        for i in range(1, len(height)):
            left.append(max(left[-1], height[i]))
        right = [height[-1]]
        for i in range(len(height)-2, -1, -1):
            right.append(max(right[-1], height[i]))
        right.reverse()
        res = 0
        for i in range(1, len(height)-1):
            this_res = min(left[i-1], right[i+1]) - height[i]
            this_res = max(this_res, 0)
            res += this_res
        return res

The above solution is O(n) time complexity, however, when the height can be updated by time, for example, new h is added to the height and we have to get the result of trapping water any time new h is added, the above solution will be not that efficient.

Stack-based solutions from here gave a better solution, it works especially good when the height can be changed with time. It is using a similar idea of Monotonic Queue. It is not that trivial, however, if you think it multiple times, you will find the beauty behind this code.

def trap(self, height):
        decreasingHeightStack, totalWaterTrapped = [], 0
        
        for i, v in enumerate(height):
            while len(decreasingHeightStack) > 0 and height[decreasingHeightStack[-1]] < v:
                bottomHeight = height[decreasingHeightStack.pop()]
                if len(decreasingHeightStack) == 0:
                    break
                leftUpperIndex = decreasingHeightStack[-1]
                heightDiff = min(height[leftUpperIndex], v) - bottomHeight
                width = i - leftUpperIndex - 1
                totalWaterTrapped += heightDiff * width
                
            decreasingHeightStack.append(i)
            
        return totalWaterTrapped

The code is rewritten in the following way:

class Solution:
    def trap(self, height: List[int]) -> int:
        decreasing_height_stack, total_water = [], 0
        
        for i, v in enumerate(height):
            while decreasing_height_stack and height[decreasing_height_stack[-1]] < v:
                bottom_height = height[decreasing_height_stack.pop()]
                if not decreasing_height_stack:break
                left_upper_index = decreasing_height_stack[-1]
                height_diff = min(height[left_upper_index], v) - bottom_height
                width = i - left_upper_index - 1
                total_water += height_diff * width
                
            decreasing_height_stack.append(i)
            
        return total_water

Reference

[1]https://medium.com/algorithms-and-leetcode/monotonic-queue-explained-with-leetcode-problems-7db7c530c1d6

[2]https://blog.csdn.net/csyifanZhang/article/details/105257494