[Leetcode] Monotonic Stack/Queue

Posted on | In , |

Monotonic Stack

Video: https://www.youtube.com/watch?v=7QEIZy1pp2o

Target problems:

  • Find smaller/greater element to the right/left of the current element

The key is to understand what does stack[-1] represents

Next Greater Element problem

Template:

1
2
3
4
5
6
7
8
9
10
11
12
def nextGreaterElement(nums):
    res = [0 for _ in range(len(nums))]
    stack = []
    for i in reversed(range(len(nums))):
        while stack and nums[i] >= stack[-1]: # increasing stack
            stack.pop()
        if not stack:
            res[i] = -1
        else:
            res[i] = stack[-1]
        stack.append(nums[i])
    return res

Leetcode 496. Next Greater Element I

Leetcode: https://leetcode.com/problems/next-greater-element-i/

  • Strictly decreasing stack
  • stack[-1] means the closest larger element to the right
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
    d = collections.defaultdict(int)
    stack = []
    res = []
    for i in reversed(range(len(nums2))):
        while stack and stack[-1] <= nums2[i]:
            stack.pop()
        if not stack:
            d[nums2[i]] = -1
        else:
            d[nums2[i]] = stack[-1]
        stack.append(nums2[i])

    for i in range(len(nums1)):
        res.append(d[nums1[i]])
    return res

Leetcode 503. Next Greater Element II

Leetcode: https://leetcode.com/problems/next-greater-element-ii/

In the brute force way, we will go on to check num[i+2], num[i+3]… and there is much redundant work here. The better way is to check the next greater number of num[i+1]. If the next greater number of num[i+1] is still not greater than num[i], go on to check its next greater number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def nextGreaterElements(self, nums: List[int]) -> List[int]:
    n = len(nums)
    newNums = []
    for i in range(n * 2 - 1):
        if i <= n - 1:
            newNums.append(nums[i])
        else:
            newNums.append(nums[i - n])
    stack = []
    res = [0 for _ in range(len(newNums))]
    for i in reversed(range(len(newNums))):
        while stack and stack[-1] <= newNums[i]:
            stack.pop()
        if not stack:
            res[i] = -1
        else:
            res[i] = stack[-1]
        stack.append(newNums[i])
    return res[:len(nums)]

739. Daily Temperature

  • Stack can store additional data (index, etc)
1
2
3
4
5
6
7
8
9
10
11
12
def dailyTemperatures(self, T: List[int]) -> List[int]:
    stack = [] # [(temp, index)]
    res = [0 for _ in range(len(T))]
    for i in reversed(range(len(T))):
        while stack and stack[-1][0] <= T[i]:
            stack.pop()
        if not stack:
            res[i] = 0
        else:
            res[i] = stack[-1][1] - i
        stack.append((T[i], i))
    return res

Area problem

42. Trapping Rain Water

Leetcode: https://leetcode.com/problems/trapping-rain-water/

  1. DP solution: 想象一束光分别从左边和右边照过array，阴影重叠部分即为积水面积
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def trap(self, height: List[int]) -> int:
    left = [0 for _ in range(len(height))]
    right = [0 for _ in range(len(height))]
    
    for i in range(len(height)):
        if i > 0 and left[i - 1] > height[i]:
            left[i] = left[i - 1]
        else:
            left[i] = height[i]
        
        j = len(height) - i - 1
        if j < len(height) - 1 and right[j + 1] > height[j]:
            right[j] = right[j + 1]
        else:
            right[j] = height[j]
    overlap = list(map(min, zip(left, right)))
    return sum(overlap) - sum(height)
  1. Monotonic stack solution
  • Note: Go from left to right and backwards, and keep finding left and right boundaries
  • stack stores index of decreasing heights
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def trap(self, height: List[int]) -> int:
    # decreasing stack, stack is for left boundary indexes, poped values are lake bottoms
    stack = []
    res = 0
    for i in range(len(height)):
        while stack and height[stack[-1]] < height[i]:
            bottom = stack.pop()
            if not stack:
                break
            minHeight = min(height[i], height[stack[-1]])
            res += (minHeight - height[bottom]) * (i - stack[-1] - 1)
            
        stack.append(i)
    return res

Leetcode 84. Largest Rectangle in Histogram

Leetcode: https://leetcode.com/problems/largest-rectangle-in-histogram/

  • Find smaller element in both left and right direction
  • 递增的时候不算面积，递减的时候算面积
  • For each pop round: area = min_popped_height * (max_poped_index - last_popped_index - 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def largestRectangleArea(self, heights: List[int]) -> int:
        # area = min_popped_height * (max_poped_index - last_popped_index - 1)
        stack = [] # increasing stack
        res = 0
        for i in range(len(heights)):
            while stack and heights[stack[-1]] >= heights[i]:
                minPop = stack.pop()
                width = i
                if stack:
                    width = i - stack[-1] - 1
                res = max(res, heights[minPop] * width)
            stack.append(i)
        # deal with the last increasing sequence of heights
        while stack:
            minPop = stack.pop()
            width = len(heights)
            if stack:
                width = len(heights) - 1 - stack[-1]
            res = max(res, heights[minPop] * width)
        return res

Leetcode 85. Maximal Rectangle

Leetcode: https://leetcode.com/problems/maximal-rectangle/

  • Repeat the solution in the problem 84 on every row
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
def maximalRectangle(self, matrix: List[List[str]]) -> int:
    if not matrix:
        return 0
    def returnLargestRec(heights):
        stack = [] # (height, i)
        boundaries = [[0, 0] for i in range(len(heights))]

        res = 0
        for i in reversed(range(len(heights))):
            # stack[-1]: the closest element that smaller than current element (to the right)
            while stack and stack[-1][0] >= heights[i]:
                stack.pop()
            if not stack:
                # heights[i] til the end
                boundaries[i][1] = len(heights) - 1
            else:
                boundaries[i][1] = stack[-1][1] - 1
            stack.append((heights[i], i))

        stack = []
        for i in range(len(heights)):
            while stack and stack[-1][0] >= heights[i]:
                stack.pop()
            if not stack:
                boundaries[i][0] = 0
            else:
                boundaries[i][0] = stack[-1][1] + 1
            stack.append((heights[i], i))
        for i, b in enumerate(boundaries):
            left, right = b
            res = max(res, (right - left + 1) * heights[i])
        return res
    
    arr = [0 for i in range(len(matrix[0]))]
    res = 0
    for row in matrix:
        for j in range(len(row)):
            if row[j] == "0":
                arr[j] = 0
            else:
                arr[j] += int(row[j])
        res = max(res, returnLargestRec(arr))
    return res

Leetcode 1504. Count Submatrices With All Ones

Leetcode: https://leetcode.com/problems/count-submatrices-with-all-ones/
Solution: https://leetcode.com/problems/count-submatrices-with-all-ones/discuss/720265/Java-Detailed-Explanation-From-O(MNM)-to-O(MN)-by-using-Stack

O(M N M) solution:

  • Use a high and low boundaries, h[k] == 1 means all elements in column k between hight and low are 1s
  • Adding a new 1 to a 1-D array: would add len(arr) new rectangles
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def numSubmat(self, mat: List[List[int]]) -> int:
    def countRow(arr):
        continuousLen = 0
        res = 0
        for num in arr:
            if num == 0:
                continuousLen = 0
            else:
                continuousLen += 1
                res += continuousLen
        return res
    res = 0
    for h in range(len(mat)):
        cnt = [1 for _ in range(len(mat[0]))]
        for l in range(h, len(mat)):
            for k in range(len(mat[0])):
                cnt[k] &= mat[l][k]
            res += countRow(cnt)
    return res

Optimize with Monotonic Stack

1
# TBA

Similar question:

  1. Number of Submatrices That Sum to Target
  2. Max Sum of Rectangle No Larger Than K

Monotonic Queue

239. Sliding Window Maximum

Leetcode: https://leetcode.com/problems/sliding-window-maximum/

  • Construct a queue with decreasing order
  • In the queue also store the index of current number so that we know if the boundary is reached and we need to popleft the item
1
2
3
4
5
6
7
8
9
10
11
12
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
    queue = collections.deque([]) # decreasing [(num, index)]
    res = []
    for i, num in enumerate(nums):
        while queue and queue[-1][0] < num:
            queue.pop()
        while queue and i - queue[0][1] >= k:
            queue.popleft()
        
        queue.append((num, i))
        res.append(queue[0][0])
    return res[k - 1:]

1499. Max Value of Equation

Leetcode: https://leetcode.com/problems/max-value-of-equation/

Solution same as 239.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:
    queue = collections.deque() # [(xj - yj, xj)]
    res = -float('inf')
    for i, point in enumerate(points):
        curSum = point[0] + point[1]
        
        while queue and point[0] - queue[0][1] > k:
            queue.popleft()
        while queue and queue[-1][0] < point[1] - point[0]:
            res = max(res, curSum + queue[0][0])
            queue.pop()
        if queue:
            res = max(res, curSum + queue[0][0])
        queue.append((point[1] - point[0], point[0]))
    return res