4. Stacks & Queues

Stack applications

0 of 5 activities0%

Reading 1

Monotonic stacks

Open

A monotonic stack keeps elements increasing or decreasing to answer “next greater/smaller” in O(n).

While scanning, pop until the top can be the answer for the current value.

Also: convert infix ideas, call stacks, backtracking state.

// next greater sketch
while (!st.empty() && a[st.back()] < a[i]) {
  ans[st.back()] = a[i];
  st.pop_back();
}
st.push_back(i);

Check 2

Open

A monotonic decreasing stack is often used for

Fill in 3

Open

Try it 4

Open

For [2,1,3] print next greater or -1.

main.cpp

Loading editor…

Program input (stdin)

Output will appear here.

Assignment 5

Open

Read a string of only (). Print yes if parentheses are balanced, else no.

main.cpp

Loading editor…