A summary of monotonic stack related problems from LeetCode with solutions in C++.
Problems:
739. Daily Temperatures
496. Next Greater Element I
503. Next Greater Element II
42. Trapping Rain Water
84. Largest Rectangle in Histogram
Problem: 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.
Case 1: Input: temperatures = [73,74,75,71,69,72,76,73], Output: [1,1,4,2,1,1,0,0]
Case 2: Input: temperatures = [30,40,50,60], Output: [1,1,1,0]
Case 2: Input: temperatures = [30,60,90], Output: [1,1,0]
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
// 递增栈
stack<int> st;
vector<int> result(T.size(), 0);
st.push(0);
for (int i = 1; i < T.size(); i++) {
if (T[i] < T[st.top()]) { // 情况一
st.push(i);
} else if (T[i] == T[st.top()]) { // 情况二
st.push(i);
} else {
while (!st.empty() && T[i] > T[st.top()]) { // 情况三
result[st.top()] = i - st.top();
st.pop();
}
st.push(i);
}
}
return result;
}
};
2. 496. Next Greater Element I
Problem: The next greater element of some element x in an array is the first greater element that is to the right of x in the same array. You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2. For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1. Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.
Case 1: Input: nums1 = [4,1,2], nums2 = [1,3,4,2], Output: [-1,3,-1]
Case 2: Input: nums1 = [2,4], nums2 = [1,2,3,4], Output: [3,-1]
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
stack<int> st;
vector<int> result(nums1.size(), -1);
if (nums1.size() == 0) { return result; }
// key: 下标元素, value: 下标
unordered_map<int,int> umap;
for (int i = 0; i < nums1.size(); i++) {
umap[nums1[i]] = i;
}
st.push(0);
for (int i = 1; i < nums2.size(); i++) {
if (nums2[i] < nums2[st.top()]) { // 情况一
st.push(i);
} else if (nums2[i] == nums2[st.top()]) { // 情况二
st.push(i);
} else { // 情况三
while (!st.empty() && nums2[i] > nums2[st.top()]) {
// 看map里是否存在这个元素
if (umap.count(nums2[st.top()]) > 0) {
// 根据map找到nums2[st.top()]在nums1中的下标
int index = umap[nums2[st.top()]];
result[index] = nums2[i];
}
st.pop();
}
st.push(i);
}
}
return result;
}
};
3. 503. Next Greater Element II
Problem: Given a circular integer array nums (i.e., the next element of nums[nums.length – 1] is nums[0]), return the next greater number for every element in nums. The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, return -1 for this number.
Case 1: Input: nums = [1,2,1], Output: [2,-1,2]
Case 2: Input: nums = [1,2,3,4,3], Output: [2,3,4,-1,4]
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> result(nums.size(), -1);
if (nums.size() == 0) { return result; }
stack<int> st;
for (int i = 0; i < nums.size() * 2; i++) {
// 模拟遍历两边nums, 注意一下都是用i % nums.size()来操作
while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
result[st.top()] = nums[i % nums.size()];
st.pop();
}
st.push(i % nums.size());
}
return result;
}
};
Problem: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Case 1: Input: height = [0,1,0,2,1,0,1,3,2,1,2,1], Output: 6
Case 2: Input: height = [4,2,0,3,2,5], Output: 9
class Solution {
public:
int trap(vector<int>& height) {
stack<int> st;
st.push(0);
int sum = 0;
for (int i = 1; i < height.size(); i++) {
while (!st.empty() && height[i] > height[st.top()]) {
int mid = st.top();
st.pop();
if (!st.empty()) {
int h = min(height[st.top()], height[i]) - height[mid];
int w = i - st.top() - 1;
sum += h * w;
}
}
st.push(i);
}
return sum;
}
};
5. 84. Largest Rectangle in Histogram
Problem: 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.
Case 1: Input: heights = [2,1,5,6,2,3], Output: 10
Case 2: Input: heights = [2,4], Output: 4
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> st;
heights.insert(heights.begin(), 0); // 数组头部加入元素0
heights.push_back(0); // 数组尾部加入元素0
st.push(0);
int result = 0;
for (int i = 1; i < heights.size(); i++) {
while (heights[i] < heights[st.top()]) {
int mid = st.top();
st.pop();
int w = i - st.top() - 1;
int h = heights[mid];
result = max(result, w * h);
}
st.push(i);
}
return result;
}
};
所有的事都是从一点一滴做起，认真做好每一步，坚持就是胜利。