Stack

#stack #monotonicstack

Problems

# Problem Difficulty Hint Tags
20 Valid Parentheses - LeetCode Easy
HintIf the bracket is opening, add it to the stack. What do we do when we reach a closed bracket? Watch for corner cases.
#string #stack
155 Min Stack - LeetCode Medium
HintUse another stack to keep track of the min. In this stack, keep track of the minimum value at that point in the other stack.
 #array #design
150 Evaluate Reverse Polish Notation - LeetCode Medium
HintPush numbers to stack and pop two numbers when we see an operand.
#array #math #stack
22 Generate Parentheses - LeetCode Medium
HintOnly add an opening bracket if less than n. Only add closing bracket if number of closing brackets is less than opening brackets. End the backtracking at open == close == n.
 #string #dynamicprogramming #backtracking
739 Daily Temperatures - LeetCode Medium
HintUse a monotonic decreasing stack with pair (temp, index). Use the difference of the stack index and the current index if a number is greater to calculate distance.
 #array #stack #monotonicstack
853 Car Fleet - LeetCode Medium
HintSort the array in reverse order. At each car, calculate the time it would take to get to the target. How would you use this and a stack to keep track of the fleets?
 #array #stack #monotonicstack #sorting
84 Largest Rectangle in Histogram - LeetCode Hard
HintHow does extending the rectangle to the left and right help us calculate the area? The key to this problem is finding the previous smallest and the next smallest elements of each element. We can use monotonic stack to keep track of each elements index of left most smallest element.
#array #stack #monotonicstack

Stacks are a data structure which support two operations, push and pop. The push command puts an element on the top of the stack while the pop command takes the top element from the stack.

In Python, stacks are implemented using Arrays using the pop and append methods.

The stack is a last in first out (LIFO) data structure and the name "stack" comes from the physical analogy of things stacked on top of each other.

Stacks are used to support nested or recursive function calls and are used to implement DFS.

Monotonic Stack

Monotonic stacks are stacks that maintain the property that their elements are always decreasing or increasing.

Decreasing monotonic stack - the bottom element is the greatest (they are placed in decreasing order)
Increasing monotonic stack - the bottom element is the smallest (they are placed in increasing order)

Corner cases