A monotonic stack is a stack whose elements are monotonically increasing or descreasing.

It’s not only about the order in the stack, it’s also about remove larger/smaller elements before pushing.

Monotonically descreasing

we need to pop smaller elements from the stack before pushing a new element:

vector<int> nums;
// fill nums
stack<int> st;

for (auto i = nums.size() - 1; i >= 0; i--) {
		while (!st.empty() && st.top() > nums[i]) {
				st.pop();
		}
		st.push(nums[i])
}
  • To push 3 to [5, 4, 2, 1], we need pop 2, 1 out first.
  • Then the stack become [5, 4, 3]

Monotonically increasing

vice versa.

vector<int> nums;
// fill nums
stack<int> st;

for (auto i = nums.size() - 1; i >= 0; i--) {
		while (!st.empty() && st.top() < nums[i]) {
				st.pop();
		}
		st.push(nums[i]);
}

Increasing vs Decreasing

  • Mono-increasing attempt to keep the result as greater as possible.
  • Vice versa.