LeetCode Day 59 Monotonic Stack (2/3)

Continue the monotonic stack exercise!

Question 1

503. Next Greater Element II

Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.

The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, return -1 for this number.

This question is similar to LC739, but it’s going to use circular arrays.

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        dp = [-1] * len(nums)
        stack = []
        for i in range(len(nums)*2):
            while(len(stack) != 0 and nums[i%len(nums)] > nums[stack[-1]]):
                    dp[stack[-1]] = nums[i%len(nums)]
                    stack.pop()
            stack.append(i%len(nums))
        return dp

Question 2

42. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

This is a common question in interviews, so it would be good to list all the approaches.

• Double pointer method
• Monotonic stack

1. The two-pointer method

The simplest Brute Force is also based on the double pointer to do: record the highest height of the left column and the highest height of the right column, you can calculate the current location of the rain area, which is calculated by the column. The current column rain area: min(the highest height of the left column, record the highest height of the right column) - the current column height.

In order to get the highest height on both sides, a double pointer is used to traverse the columns, traversing to both sides at every column. This causes double counting and is optimised:

We record the highest height on the left at each position on an array (maxLeft) and the highest height on the right on an array (maxRight), which avoids double counting.

The current position, the highest height on the left is the maximum of the highest height on the left of the previous position and this height.

That is, traverse from left to right: maxLeft[i] = max(height[i], maxLeft[i - 1]);

Iterate from right to left: maxRight[i] = max(height[i], maxRight[i + 1]);

class Solution:
    def trap(self, height: List[int]) -> int:
        leftheight, rightheight = [0]*len(height), [0]*len(height)
 
        leftheight[0]=height[0]
        for i in range(1,len(height)):
            leftheight[i]=max(leftheight[i-1],height[i])
        rightheight[-1]=height[-1]
        for i in range(len(height)-2,-1,-1):
            rightheight[i]=max(rightheight[i+1],height[i])
 
        result = 0
        for i in range(0,len(height)):
            summ = min(leftheight[i],rightheight[i])-height[i]
            result += summ
        return result

1. Monotonous stacks

2.1 Ideas:

2.1.1 Firstly, the monotonic stack calculates rain in the direction of the rows. 2.1.2 Using the order of elements in the monotonic stack The order from the head of the stack (elements are popped from the head of the stack) to the bottom of the stack should be from smallest to largest. This is because once you realise that the height of the added column is greater than the height of the stack head element, the notch will appear, the stack head element will be the column at the bottom of the notch, the second element from the stack head will be the column to the left of the notch, and the added element will be the column to the right of the notch. 2.1.3 What to do if you encounter a column of the same height. When we encounter the same element, we update the stack subscript, that is, we pop out the stack element (the old subscript) and add the new element (the new subscript) to the stack. This is because when we ask for the width, if we encounter a column of the same height, we need to use the rightmost column to calculate the width. 2.1.4 What values to keep in the stack Using a monotonic stack, the rain area is also calculated from the length * width. The length is calculated from the height of the columns and the width is calculated from the subscripts between the columns. So is it necessary to store an element of type pair<int, int> in the stack to save the height and subscripts of the columns? In fact, we don’t need to store the subscripts in the stack, if we want to know the corresponding height, we can use height[stack.top()] to know the corresponding height of the subscripts that are popped up.

2.2 Monotonic stack processing logic

The following logic is mainly three cases:

• Case 1: the height of the currently traversed element (column) is less than the height of the top element of the stack height[i] < height[stack.top()]
• Case 2: the height of the currently traversed element (column) is equal to the height of the top element height[i] == height[st.top()].
• Case 3: the height of the currently traversed element (column) is greater than the height of the top element of the stack height[i] > height[st.top()]

First add the column with subscript 0 to the stack, st.push(0);. The stack holds the elements we’ve traversed, so add subscript 0 first. Then start traversing all the columns from subscript 1, for (int i = 1; i < height.size(); i++).

If the height of the currently traversed element (column) is less than the height of the top element of the stack, add that element to the stack, since the stack is meant to be kept in smallest-to-largest order (from the head of the stack to the bottom of the stack).

If the height of the currently traversed element (column) is equal to the height of the top element, update the top element, because if you encounter a column of the same height, you need to use the rightmost column to calculate the width.

If the current traversal of the element (column) height is greater than the height of the top stack element, at this time there is a notch

Take the top element of the stack and pop out the top element of the stack, which is the bottom of the notch, i.e., the middle position, with the subscript mid and the corresponding height as height[mid].

The top element of the stack at this point, st.top(), is the left position of the notch, subscripted st.top(), with a corresponding height of height[st.top()].

The currently traversed element, i, is the position to the right of the notch, subscripted by i, with the corresponding height being height[i].

At this point it can be found that it is actually the top of the stack and the next element on the top of the stack and the element to be added to the stack, three elements to catch the water!

Then the height of the rain is min(height of the left side of the groove, height of the right side of the groove) - height of the bottom of the groove, the code is: int h = min(height[st.top()], height[i]) - height[mid];

The width of the rain is the subscript of the right side of the notch - the subscript of the left side of the notch - 1 (because only the width of the middle is sought), the code is: int w = i - st.top() - 1 ;

The volume of the current notch rain is: h * w.

class Solution:
    def trap(self, height: List[int]) -> int:
        stack = [0]
        result = 0
        for i in range(1, len(height)):
            while stack and height[i] > height[stack[-1]]:
                mid_height = stack.pop()
                if stack:
                    h = min(height[stack[-1]], height[i]) - height[mid_height]
                    w = i - stack[-1] - 1
                    result += h * w
            stack.append(i)
        return result