Monotonic Stack
Table of Contents
1 Introduction to monotonic stack
A monotonic stack is a stack whose elements are monotonically increasing or decreasing.
If we pop greater elements from the stack before pushing a new element, the stack will increase from bottom to top. If we pop lesser elements, the stack will decrease.
The typical paradigm for an increasing monotonic stack is like:
for (int i = 0; i < A.size(); i++) { while (!stk.empty() && stk.top() > A[i]) { stk.pop(); } stk.push(A[i]); }
2 What can monotonically increasing stacks do?
Monotonically increasing stacks can be used to solve a variety of algorithmic problems. One common use case is for finding the nearest greater element in an array. By maintaining a stack of elements in increasing order, we can quickly determine the next greater element for each element in the array. Monotonically increasing stacks can also be used for finding the maximum area of a histogram, as well as for solving problems related to dynamic programming and graph algorithms.
2.1 To find the previous less element of each element in a vector with O(n) time.
What is the previous less element of an element in a vector? Suppose there is a vector [3, 8, 9, 6], for each element 3, 8, 9, and 6:
- There is no previous less element for 3.
- The previous less element of 8 is 3.
- The previous less element of 9 is 8.
- The previous less element of 6 is 3.
To obtain the previous less element of each element in a vector, we can modify the paradigm as follows:
int n = A.size(); vector<int> prevLessVal(n); for (int i = 0; i < n; i++) { while (!stk.empty() && stk.top() > A[i]) { stk.pop(); } prevLessVal[i] = stk.empty()? -1: stk.top(); stk.push(A[i]); }
Sometimes we store indices instead of values in the stack. A value of -1 can now mean that: the index of its previous value is virtually at the position one element prior to the beginning of the vector, such as prevLessIdx following.
A values: INT_MIN [3, 8, 9, 6] A indices: -1 0 1 2 3 prevLessVal: [-1, 3, 8, 3] prevLessIdx: [-1, 0, 1, 0]
Code with indices stored:
for (int i = 0; i < n; i++) { while (!stk.empty() && A[stk.top()] > A[i]) { stk.pop(); } prevLessIdx[i] = stk.empty()? -1: stk.top(); stk.push(i); }
Storing indices can be helpful when we need to calculate the distance between an element and its previous less element. It is particularly useful in scenarios where we need to perform complex calculations or comparisons based on the relative positions of elements in the vector.
2.2 To find the next less element of each element in a vector with O(n) time.
Similarly, for the vector [3, 8, 9, 6], the next less element of each element:
- The is no next less element for 3.
- The next less element of 8 is 6.
- The next less element of 9 is 6.
- The is no next less element for 6.
This can be done in the same way, but traversing the vector backward:
int n = A.size(); vector<int> nextLessVal(n); for (int i = n - 1; i >= 0; i--) { while (!stk.empty() && stk.top() > A[i]) { stk.pop(); } nextLessVal[i] = stk.empty()? -1: stk.top(); stk.push(A[i]); }
Similarly, we sometimes store indices of next smaller elements, as in the following example:
vector<int> nextLessIdx(n); for (int i = n - 1; i >= 0; i--) { while (!stk.empty() && A[stk.top()] > A[i]) { stk.pop(); } nextLessIdx[i] = stk.empty()? n: stk.top(); stk.push(i); }
Note that in this example, we use 'n' instead of '-1' when there is no next less element. It represents that the next less value is at the end of the vector, so that to be simpler in logic when calculating distances.
We can also find the next smaller elements by traversing the vector forward, but setting the next smaller element of an element before popping it from the stack:
vector<int> nextLessIdx(n, n); for (int i = 0; i < n; i++) { while (!stk.empty() && A[stk.top()] > A[i]) { nextLessIdx[stk.top()] = i; stk.pop(); } stk.push(A[i]); }
This way we are able to obtain both previous and next less elements in one pass, such as:
vector<int> prevLessIdx(n, -1); vector<int> nextLessIdx(n, n); for (int i = 0; i < n; i++) { while (!stk.empty() && A[stk.top()] > A[i]) { nextLessIdx[stk.top()] = i; stk.pop(); } prevLessIdx[i] = stk.empty()? -1: stk.top(); stk.push(i); }
3 What can monotonically decreasing stacks do?
On the other hand, monotonically decreasing stacks can help find the previous or next greater element of each element in a vector with O(n) time.
The code to find the values of previous greater elements would be:
int n = A.size(); vector<int> prevGreaterVal(n); for (int i = 0; i < n; i++) { while (!stk.empty() && stk.top() < A[i]) { stk.pop(); } prevGreaterVal[i] = stk.empty()? -1: stk.top(); stk.push(A[i]); }
Here, I will let you practice coding to find indices of previous and next greater elements in a vector in one pass.
4 When are monotonic stacks used?
We can use the extra space of a monotonic stack to reduce the time complexity. To get the nearest smaller or greater element (depending on the stack type) is just an O(1) operation. Therefore, to have the previous less elements (again, can be next less elements, previous or next greater elements depending on the stack type) of all the elements in a vector is O(n) time.
It also helps to maintain maximum and minimum elements in the range and keeps the order of elements in the range. So we don't need to compare elements one by one again to get the minimum or maximum in the range.
5 The applications of monotonic stacks
How to use monotonic stacks to solve problems? Let us look at a basic example on LeetCode - 739. Daily Temperatures
The answer will be an array of number of days (distance) you have to wait to get a warmer temperature (next greater element). We apply the paradigm of a decreasing monotonic stack:
vector<int> dailyTempeature(vector<int>& temperatures) { stack<int> stk; int n = temperatures.size(); vector<int> res(n); for (int i = n - 1; i >= 0; i--) { while (!stk.empty() && temperatures[stk.top()] <= temperatures[i]) stk.pop(); if (!stk.empty()) res[i] = stk.top() - i; stk.push(i); } return res; }
The next example is 901. Online Stock Span. Each time calling next(), we need to find the maximum number of consecutive days for which the price is less than or equal to the price of that day. To solve this problem, we can think of the stock prices as elements in an array, and the days as indices. The objective is to find the previous greater element for each element in the array.
class StockSpanner { int index = 0; stack<pair<int, int>> stk; //price, index public: int next(int price) { while (!stk.empty() && stk.top().first <= price) stk.pop(); int res = stk.empty()? index + 1 : index - stk.top().second; stk.push({price, index}); index++; return res; } };
We maintain a monotonic decreasing stack that stores both indices and prices. Each time, we pop the prices that are equal to or less than the current price. The top of the stack represents the previous greater element, and we calculate the difference in indices. An empty stack means that there is no such element, and the span is equal to the index plus one.
If we iterate through the vector twice, we can obtain the previous less elements, next less elements, previous greater elements, or next greater elements of a circular array. An example of this is 503. Next Greater Element II.
vector<int> nextGreaterElements(vector<int>& nums) { int n = nums.size(); vector<int> res(n, -1); stack<int> stk; for (int i = 0; i < n * 2; i++) { while (!stk.empty() && nums[stk.top()] < nums[i % n]) { res[stk.top()] = nums[i % n]; stk.pop(); } stk.push(i % n); } return res; }
Note that the vector is traversed twice, and the index 'i' is modulated by the length of the vector to ensure having the correct index.
The next example is 496. Next Greater Element I. Given two arrays of integers, for each element in the first array, we need to find the next greater element in the second array that has the same value. The naive way to solve this problem is to search through the second array for each element in the first array, which takes O(n2) time.
However, a more efficient solution is to create a hash map with the second array. In each pair, the key is an element value, and the value is its next greater element in the array. By using the hash map (with space complexity O(n)), the time complexity can be improved to O(n).
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) { stack<int> stk; unordered_map<int, int> nextGreater; for (int no : nums2) { while (!stk.empty() && stk.top() < no) { nextGreater[stk.top()] = no; stk.pop(); } } vector<int> res; for (int no : nums1) { if (nextGreater.find(no) != nextGreater.end()) res.push_back(nextGreater[no]); else res.push_back(-1); } return res; }
Sometimes, even if the keywords 'previous/next' and 'less/greater' are not explicitly stated in the problem, we can still infer them by analyzing the question, such as in 402. Remove K Digits.
In this problem, we need to find the smallest number possible by removing 'k' digits, which means that the digits to be removed should be as large and significant as possible. In other words, a previous greater number has the priority to be removed.
Unlike Java, strings in C++ are mutable. For convenience, we can modify the string as if it were a stack using pushback() and popback(). For each digit in the given number, if we have quota (k) and the previous digit is greater, we can pop it from the stack.
string removeKdigits(string num, int k) { string res{}; //stack for (char dig : num) { while (!res.empty() && k > 0 && dig < res.back()) { res.pop_back(); --k; } res.push_back(dig); } // numbers are already in a non decreasing order while (!res.empty() && k > 0) { res.pop_back(); --k; } // remove leading 0s while (!res.empty() && res[0] == '0') res.erase(0, 1); return res.empty()? "0" : res; }
The code can be divided into two parts. The first part is the typical paradigm of a monotonic stack. The second part handles two corner cases. The first case is when we have finished pushing all the digits onto the stack, but there is still quota (k) left to remove. In this case, we can remove the remaining larger digits from the stack. The second case is when we need to remove any leading zeros that may have been added to the front of the number.
316. Remove Duplicate Letters is another example though the keywords are not explicitly state in the problem. Since the result is expected to be the smallest lexicographical order, the previous greater letters are to be removed.
string removeDuplicateLetters(string s) { unordered_map<char, int> last; for (int i = 0; i < s.size(); i++) last[s[i]] = i; stack<char> stk; unordered_set<char> seen; for (int i = 0; i < s.size(); i++) { if (seen.count(s[i])) continue; while (!stk.empty() && stk.top() > s[i] && last[stk.top()] > i) { seen.erase(stk.top()); stk.pop(); } seen.insert(s[i]); stk.push(s[i]); } string res{}; while (!stk.empty()) { res = stk.top() + res; stk.pop(); } return res; }
In the code, we first create a hash map to record the last index for every character in the string. When traversing the string, we push each character onto a stack, and if any previous character (in the stack) is a non-last duplicate and greater than the current one, we pop it from the stack. This ensures that the result will be in the stack in reverse order.
Then, in 1944. Number of Visible People in a Queue, we need to count the number of people in a queue who can be seen by others in front of them.
To solve this problem, we need to pop the next shorter people on the right, since they will be blocked by the i-th person and not seen by anyone in the front. Each time we pop a person, we increase the count since that person can be seen by the i-th person. Additionally, we also increase the count if there is a next greater person in the stack, because person can also be seen by the i-th person.
vector<int> canSeePersonsCount(vector<int>& heights) { int n = heights.size(); vector<int> res(n); stack<int> stk; for (int i = n - 1; i >= 0; i--) { while (!stk.empty() && heights[i] > stk.top()) { stk.pop(); // shorter people on the right will not be seen anymore ++res[i]; // i can see those shorter people } if (!stk.empty()) ++res[i]; // i can see 1 more taller person stk.push(heights[i]); } return res; }
Sometimes we need to find both previous and next less (or greater) elements, such as in 84. Largest rectangle in Hisogram.
We can do this in one pass using a stack. For each index, we can calculate the maximum rectangle that can be formed using its height and the width between its previous and next less element. We can then compare all these areas and return the maximum value.
int largestRectangleArea(vector<int>& heights) { int n = heights.size(); vector<int> prevLess(n, -1), nextLess(n, n); stack<int> stk; for (int i = 0; i < n; i++) { while (!stk.empty() && heights[stk.top()] >= heights[i]) { nextLess[stk.top()] = i; stk.pop(); } prevLess[i] = stk.empty()? -1: stk.top(); stk.push(i); } int res = 0; for (int i = 0; i < n; i++) { res = max(res, heights[i] * (nextLess[i] - prevLess[i] - 1)); } return res; }
1793. Max Score of a Good Subarray is another example where we need to find both previous and next less elements.
To find the maximum score of a good subarray, we can iterate over all possible subarrays and check if the range between the previous and next less elements contains the integer k. If it does, we can calculate the score of the subarray by multiplying the minimum value in the subarray by the length of the subarray. We can then compare the score to the current maximum value and update it accordingly.
int maximumScore(vector<int>& nums, int k) { int n = nums.size(); vector<int> prevLess(n, -1), nextLess(n, n); stack<int> stk; for (int i = 0; i < n; i++) { while (!stk.empty() && nums[stk.top()] >= nums[i]) { nextLess[stk.top()] = i; stk.pop(); } prevLess[i] = stk.empty()? -1: stk.top(); stk.push(i); } int res = 0; for (int i = 0; i < n; i++) { if (prevLess[i] < k && k < nextLess[i]) res = max(res, nums[i] * (nextLess[i] - prevLess[i] - 1)); } return res; }
42. Trapping Rain Water is another problem that can be solved similarly, by finding the maximum values from the beginning and end of the array in two passes. The amount of water that can be trapped above each element is then decided by the lower of the two maximum values minus its height.
int trap(vector<int>& height) { int n = height.size(); vector<int> rMax(n), lMax(n); stack<int> stk; for (int i = 0; i < n; i++) { while (!stk.empty() && height[i] >= stk.top()) stk.pop(); if (stk.empty()) stk.push(height[i]); lMax[i] = stk.top(); } // new stack stk = move(stack<int>()); for (int i = n - 1; i >= 0; i--) { while(!stk.empty() && height[i] >= stk.top()) stk.pop(); if (stk.empty()) stk.push(height[i]); rMax[i] = stk.top(); } int res = 0; for (int i = 0; i < n; i++) { res += min(rMax[i], lMax[i]) - height[i]; } return res; }
Although there is no need to use an additional stack to find the maximum values. A solution without using a stack is as follows.
int trap(vector<int>& height) { int n = height.size(); vector<int> rMax(n), lMax(n); int curMax = 0; for (int i = 0; i < n; i++) { curMax = max(curMax, height[i]); lMax[i] = curMax; } curMax = 0; for (int i = n - 1; i >= 0; i--) { curMax = max(curMax, height[i]); rMax[i] = curMax; } int res = 0; for (int i = 0; i < n; i++) { res += min(rMax[i], lMax[i]) - height[i]; } return res; }
However, it can also be solved with O(1) space complexity. Since the height of each element is determined by the lower of the maximum height backward and forward, we can have two pointers from the beginning and the end of the array, and each time move the pointer with the lower height toward the center.
At each index, we calculate the amount of water that can be trapped above it by finding the lower of the two maximum heights and subtracting its height from that value. We do not know how high the other side can be at this point, but it does not matter. The code for this approach would look like:
int trap(vector<int>& height) { int l = 0, r = height.size() - 1; int lMax = height[l], rMax = height[r]; int res = 0; while (l < r) { if (height[l] < height[r]) { ++l; lMax = max(lMax, height[l]); res += lMax - height[l]; } else { --r; rMax = max(rMax, height[r]); res += rMax - height[r]; } } return res; }
907. Sum of Subarray Minimums is another problem where it is not obvious how to calculate the sum of subarray minimums. Instead of calculating for every subarray, it is easier to think in terms of each index.
For each index, when the element is the minimum in a subarray, all the previous and next values are greater. The longest possible subarray with this property has the range from its previous less element to its next less element. The length of such a subarray can be calculated as (i - prevLess[i]) * (nextLess[i] - i), where the left-hand side is the range from 1 (the element itself) to the distance to its previous less element, and the right-hand side is the range from 1 (the element itself) to the distance to its next less element.
int sumSubarrayMins(vector<int>& arr) { int n = arr.size(); vector<int> prevLess(n, -1), nextLess(n, n); stack<int> stk; for (int i = 0; i < n; i++) { while (!stk.empty() && arr[stk.top()] > arr[i]) { nextLess[stk.top()] = i; stk.pop(); } prevLess[i] = stk.empty()? -1: stk.top(); stk.push(i); } int res = 0; for (int i = 0; i < n; i++) { res = (res + arr[i] * (i - prevLess[i]) * (nextLess[i] - i)) % mod; } return res; }
2866. Beautiful Towers II is another interesting problem. For each index, we can think of it as the top of a mountain, and we can accumulate the heights of the towers to the left and right of the mountain in two separate vectors.
To calculate the beauty of the mountain, we can use a stack to keep track of the towers to the left (or right) of the mountain. For the left-hand side, we can pop all the towers with greater heights than the current tower, since they can have up to maxHeights[i] height. A lower tower in the stack is the boundary, and we need to add the sum of the tower heights to the left of the boundary to the beauty of the mountain. This can be calculated as maxHeights[i] multiplied by the distance to the previous less element.
The same approach can be used for the right-hand side of the mountain. We can then return the sum of the beauties of all the mountains.
long long maximumSumOfHeights(vector<int>& maxHeights) { int n = maxHeights.size(); vector<long long> left(n), right(n); // sum of heights to the left, right stack<int> stk; for (int i = 0; i < n; i++) { while (!stk.empty() && maxHeights[stk.top()] > maxHeights[i]) stk.pop(); if (stk.empty()) left[i] = (long long)maxHeights[i] * (i + 1); else left[i] = left[stk.top()] + (long long)maxHeights[i] * (i - stk.top()); stk.push(i); } stk = move(stack<int>()); long long res{}; for (int i = n - 1; i >= 0; i--) { while (!stk.empty() && maxHeights[stk.top()] > maxHeights[i]) stk.pop(); if (stk.empty()) right[i] = (long long)maxHeights[i] * (n - i); else right[i] = right[stk.top()] + (long long)maxHeights[i] * (stk.top() - i); stk.push(i); res = max(res, left[i] + right[i] - maxHeights[i]); } return res; }
I hope the comments have helped you understand monotonic stacks better. If you are interested in solving more problems, please check out LeetCode - Monotonic Stack tag.
Created: 2024-02-21 Wed 13:12
No comments:
Post a Comment