Remarks

  • A stack is a collection that is Last-In-First-Out(LIFO).

Implementation

An implementation of Stack using linked list.

class Stack(object):
    class Node(object):
        def __init__(self, item=None):
            self.item = item
            self.next = None

    def __init__(self):
        self.node = None
        self._n = 0

    @property
    def is_empty(self):
        return not self.node

    def __len__(self):
        return self.n

    def push(self, item):
        prev = self.node
        self.node = self.Node(item)
        self.node.next = prev
        self._n += 1

    def pop(self):
        assert not self.is_empty, "Stack is empty"
        item = self.node.item
        self.node = self.node.next
        self._n -= 1
        return item

    def peek(self):
        return self.node.item

Monotonic Stack

MIS

MDS

  • 456. 132 Pattern

    Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].
    Return true if there is a 132 pattern in nums, otherwise, return false.

def find132pattern(nums):
    n = len(nums)
    min_upto = [nums[0]]
    for num in nums[1:]:
        min_upto.append(min(min_upto[-1], num))
    
    stack = [0]
    for i, num in enumerate(nums[1:], 1):
        while stack and nums[stack[-1]] < num: stack.pop()
        if stack and nums[stack[-1]] > num > min_upto[stack[-1]]: return True
        stack.append(i)
    return False
  • 84. Largest Rectangle in Histogram

    Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

def largestRectangleArea(heights):
    heig hts.append(0)
    stack = [-1]
    max_area = 0
    for i, height in enumerate(heights):
        while stack and heights[stack[-1]] > height:
            h = heights[stack.pop()]
            w = i - stack[-1] - 1
            max_area = max(max_area, h * w)
        stack.append(i)
    heights.pop()
    return max_area

739. Daily Temperatures

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Monotonic decreasing stack

# left to right
def dailyTemperatures(temperatures):
    result = [0] * len(temperatures)
    stack = []
    for day in range(len(temperatures)):
        temp = temperatures[day]
        while stack and temp > temperatures[stack[-1]]:
            prev_day = stack.pop()
            result[prev_day] = day - prev_day
        stack.append(day)
    return result

# right to left n
def dailyTemperatures(temperatures):
    result = [0] * len(temperatures)
    stack = []
    for day in range(len(temperatures) - 1, -1, -1):
        temp = temperatures[day]
        while stack and temp >= temperatures[stack[-1]]:
            stack.pop()
        if stack:
            result[day] = stack[-1] - day
        stack.append(day)
    return result