Monotone Stack

Algorithms
stack
Catalogue
  1. 1. Next Greater Element
    1. 1.1. 496. Next Greater Element I
    2. 1.2. 503. Next Greater Element II
    3. 1.3. 84. Largest Rectangle in Histogram
      1. 1.3.1. Solution1. middle heart open flower
      2. 1.3.2. Solution2. Stack
    4. 1.4. 42. Trapping Rain Water

Next Greater Element

496. Next Greater Element I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def nextGreaterElement(self, findNums, nums):
        dic = {}
        stack = []
        for num in nums:
            while stack and num > stack[-1]:
                dic[stack.pop()] = num
            stack.append(num)

        res = []
        for num in findNums:
            if num not in dic:
                res.append(-1)
            else:
                res.append(dic[num])
        return res

503. Next Greater Element II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def nextGreaterElements(self, nums):
        n = len(nums)
        res = [-1] * n
        stack = []
        for i in range(n):
            while stack and nums[stack[-1]] < nums[i]:
                res[stack.pop()] = nums[i]
            stack.append(i)

        for i in range(n):
            while stack and nums[stack[-1]] < nums[i]:
                res[stack.pop()] = nums[i]
        return res

84. Largest Rectangle in Histogram

Solution1. middle heart open flower

for each index i, walk right to find the left border and right border.
Time = O($n^2$)

Solution2. Stack

  • Use a Stack to store all the indices of the columns that form an ascending order stack that stores the indeices in ascending order. [1, 5, 6
  • When scanning the element with index = 4, M[4] = 2 < M[3] = 6, so we keep checking left column of index 4, and calculate the area of index 3,2 and pop them out of the stack, after this step, the stack is [1, 5
  • Priciple, to maintain the stack to make sure the colums shose indices are stored in the stack from an sacending order.
  • TimeO(n), because every single element can only be inserted and popped out of the stack once and only once.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def largestRectangleArea(self, heights):
        stack = []
        hs = heights + [0]
        i = 0
        res = 0
        while i <= len(hs)-1:
            if not stack or hs[stack[-1]] < hs[i]:
                stack.append(i)
                i += 1
            else:
                idx = stack.pop()
                res = max(res, hs[idx] * (i if not stack else (i-stack[-1]-1)) )
        return res

42. Trapping Rain Water

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def trap(self, height):
        n = len(height)
        stack = []
        res = 0
        i = 0
        while i <= n-1:
            if not stack or height[i] <= height[stack[-1]]:
                stack.append(i)
                i += 1
            else:
                t = stack.pop()
                if not stack:
                    continue
                res += (min(height[stack[-1]], height[i]) - height[t]) * (i - stack[-1] - 1)
        return res
Share