单调栈
所谓单调栈，是指栈内的元素是单调的，即单调递增或单调递减。
单调栈一般用来求一维数组中任一元素左边或(和)右边第一个大于或小于的元素位置或距离。原理如下：
例如，求一维数组中任一元素离右边第一个大于该元素的元素的距离。nums = [73,74,75,71,69,72,76,73]，用result存储结果。可以看出最终result = [1,1,4,2,1,1,0,0]。我们用单调栈来计算一下。
因为是求的右边第一个大于的元素的距离，所以从最左边的元素开始入栈，栈内存储的是元素的下标，又因为求的是大于的元素，所以遇见比当前栈顶小的元素就将该元素入栈，遇见更大的就将当前栈顶元素出栈（即维持的是一个单调递减的栈），并且存储到result数组中，存储的结果应为result[stack.top()] = i - stack.top()，即当前元素的下标减去栈顶元素的下标得到距离。重复此过程可得到正确的结果。下面看几个例子吧。
739. 每日温度
这个题其实就是上面举的例子，按上面说的做即可，注意要判断栈是否为空。
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
stack<int> less_st;
less_st.push(0);
int n = temperatures.size();
vector<int> result(n, 0);
for (int i = 1; i < n; i++) {
while (!less_st.empty() && temperatures[i] >temperatures[less_st.top()]) {
result[less_st.top()] = i - less_st.top();
less_st.pop();
}
less_st.push(i);
}
return result;
}
};
496. 下一个更大元素 I
这个题和上面那个题也差不多，只不过要在两个数组之间查找一下，因为没有重复元素，所以使用unordered_map。
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
vector<int> ans(nums1.size(), -1);
unordered_map<int, int> position;
for (int i = 0; i < nums2.size(); i++) {
position.insert(pair<int, int>(nums2[i], i));
}
for (int i = 0; i < nums1.size(); i++) {
ans[i] = position[nums1[i]];
}
vector<int> temp(nums2.size(), -1);
stack<int> st;
st.push(0);
for (int i = 1; i < nums2.size(); i++) {
while (!st.empty() && nums2[i] > nums2[st.top()]) {
temp[st.top()] = nums2[i];
st.pop();
}
st.push(i);
}
for (int i = 0; i < nums1.size(); i++) {
ans[i] = temp[ans[i]];
}
return ans;
}
};
503. 下一个更大元素 II
这个题其实和上面那个题差不多，只不过要循环两遍，可以直接下面这么循环
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> result(n, -1);
stack<int> st;
st.push(0);
for (int i = 0; i < n * 2; i++) {
while (!st.empty() && nums[i % n] > nums[st.top()]) {
result[st.top()] = nums[i % n];
st.pop();
}
st.push(i % n);
}
return result;
}
};
也可以像下面这么笨拙一点循环。
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> result(n, -1);
stack<int> st;
st.push(0);
for (int i = 0; i < n; i++) {
while (!st.empty() && nums[i] > nums[st.top()]) {
result[st.top()] = nums[i];
st.pop();
}
st.push(i);
}
int num_end = st.top();
for (int i = 0; i < num_end; i++) {
while(!st.empty() && nums[i] > nums[st.top()]) {
result[st.top()] = nums[i];
st.pop();
}
}
return result;
}
};
42. 接雨水
我们按照列来计算，即计算每一列可以装多少雨水，观察可以发现，每一列可接的雨水量取决于min(左边最高的柱子，右边最高的柱子) - 当前柱子高度，如果结果小于等于0说明接不了雨水。
所以可以遍历每一个柱子，找出两边符合条件的柱子进行计算，时间复杂度为O(n^2)，代码如下：
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int ans = 0;
for (int i = 0; i < n; i++) {
if (i == 0 || i == n - 1)
continue;
int left = height[i], right = height[i];
for (int j = i - 1; j >= 0; j--) {
if (height[j] > left)
left = height[j];
}
for (int j = i + 1; j < n; j++) {
if (height[j] > right)
right = height[j];
}
int h = min(left, right) - height[i];
if (h > 0)
ans += h;
}
return ans;
}
};
不过这个代码是有超时的，因为有很多重复计算，左边右边的柱子被多次计算。所以我们可以利用动态规划的思想把每次计算的结果保存下来，dp_left[i]表示的是第0到i个柱子中最高的，dp_right[i]表示的是第i到第n - 1个柱子中最高的，
dp_left[i] = max(height[i], dp_left[i - 1])
dp_right[i] = max(height[i], dp_right[i + 1])
进一步精简的话可以用两个变量直接代替数组。代码如下：
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int ans = 0;
vector<int> max_left(n, 0);
vector<int> max_right(n, 0);
max_left[0] = height[0];
max_right[n - 1] = height[n - 1];
for (int i = 1; i < n; i++) {
max_left[i] = max(max_left[i - 1], height[i]);
}
for (int i = n - 2; i >= 0; i--) {
max_right[i] = max(max_right[i + 1], height[i]);
}
for (int i = 0; i < n; i++) {
if (i == 0 || i == n - 1)
continue;
int h = min(max_left[i], max_right[i]) - height[i];
if (h > 0)
ans += h;
}
return ans;
}
};
这样时间复杂度就降为O(n)了。
也可以用单调栈来做，单调栈里的元素从栈底到栈头（栈头压入弹出）递减的顺序，遍历过程中，如果遇到更小的元素压入栈中，如果遇见相等的元素要把原来的栈顶元素弹出再压入新的元素，这样是为了保持宽度的正确，遇到更大就可以算相应的接水量了，接水量的计算公式为长 * 宽。讲的不太清楚，具体可以看这个博客柱状图中最大的矩形。代码如下：
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
stack<int> st;
st.push(0);
int sum = 0;
for (int i = 1; i < n; i++) {
if (height[i] < height[st.top()]) {
st.push(i);
}
else if (height[i] == height[st.top()]) {
st.pop();
st.push(i);
}
else {
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];
sum += h * (i - st.top() - 1);
}
}
st.push(i);
}
}
return sum;
}
};
84. 柱状图中最大的矩形
这个题和上面那道题差不多，只不过一个求的是自己两侧比自己高的柱子，这个求的是自己两侧比自己低的柱子。单调栈的代码如下：
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
heights.push_back(0);
heights.insert(heights.begin(), 0);
stack<int> st;
st.push(0);
int sum = 0;
for (int i = 1; i < heights.size(); i++) {
while (!st.empty() && heights[i] < heights[st.top()]) {
int mid = st.top();
st.pop();
int w = i - st.top() - 1;
sum = max(sum, w * heights[mid]);
}
st.push(i);
}
return sum;
}
};
总结
单调栈一般用于求任一元素左侧或（和）右侧第一个大于或小于的元素位置。特别要注意的是一般栈中存储的是元素的下标，所以使用的时候要转化一下。