今天来学习单调栈的相关知识。
首先先来看一下单调栈的应用场景和原理。
应用场景：
通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。
原理：
单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是整个数组只需要遍历一次。
更直白来说，就是用一个栈来记录我们遍历过的元素，因为遍历数组的时候，不知道之前都遍历了哪些元素，以至于遍历一个元素找不到是不是之前遍历过一个更小的，所以需要用一个容器（这里用单调栈）来记录遍历过的元素。
在使用单调栈的时候首先要明确如下几点：
1.单调栈里存放的元素是什么？
单调栈里只需要存放元素的下标i就可以了，如果需要使用对应的元素，直接T[i]就可以获取。
2. 单调栈里元素是递增呢？ 还是递减呢？
注意以下讲解中，顺序的描述为从栈头到栈底的顺序。
这里要使用递增循序（再强调一下是指从栈头到栈底的顺序），因为只有递增的时候，栈里要加入一个元素i的时候，才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i。
即：如果求一个元素右边第一个更大元素，单调栈就是递增的，如果求一个元素右边第一个更小元素，单调栈就是递减的。
使用单调栈主要有三个判断条件。
- 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
- 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
- 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
这样，我们来看一道题目：739. 每日温度 - 力扣（LeetCode）
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
C++代码如下：
// 版本一
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;
}
};第一次接触的时候，可以根据代码来模拟一遍，把过程搞清楚。
接着看下一道：496. 下一个更大元素 I - 力扣（LeetCode）
可以看出最后是要求nums1的每个元素在nums2中下一个比当前元素大的元素，那么就要定义一个和nums1一样大小的数组result来存放结果。
这么定义这个result数组初始化应该为多少呢？
题目说如果不存在对应位置就输出 -1 ，所以result数组如果某位置没有被赋值，那么就应该是是-1，所以就初始化为-1。
在遍历nums2的过程中，我们要判断nums2[i]是否在nums1中出现过，因为最后是要根据nums1元素的下标来更新result数组。
注意题目中说是两个没有重复元素 的数组 nums1 和 nums2。
没有重复元素，就可以用map来做映射了。根据数值快速找到下标，还可以判断nums2[i]是否在nums1中出现过。
C++中，当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的。
栈头到栈底的顺序，要从小到大，也就是保持栈里的元素为递增顺序。只要保持递增，才能找到右边第一个比自己大的元素。
接下来就要分析如下三种情况，一定要分析清楚。
1.情况一：当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
此时满足递增栈（栈头到栈底的顺序），所以直接入栈。
2.情况二：当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
如果相等的话，依然直接入栈，因为我们要求的是右边第一个比自己大的元素，而不是大于等于！
3.情况三：当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
此时如果入栈就不满足递增栈了，这也是找到右边第一个比自己大的元素的时候。
判断栈顶元素是否在nums1里出现过，（注意栈里的元素是nums2的元素），如果出现过，开始记录结果。
记录结果这块逻辑有一点小绕，要清楚，此时栈顶元素在nums2数组中右面第一个大的元素是nums2[i]
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;
unordered_map<int, int> umap; // key:下标元素，value：下标
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()]) {
if (umap.count(nums2[st.top()]) > 0) { // 看map里是否存在这个元素
int index = umap[nums2[st.top()]]; // 根据map找到nums2[st.top()] 在 nums1中的下标
result[index] = nums2[i];
}
st.pop();
}
st.push(i);
}
}
return result;
}
};然后接着看下一题：503. 下一个更大元素 II - 力扣（LeetCode）
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
直接把两个数组拼接在一起，然后使用单调栈求下一个最大值不就行了！
确实可以！
将两个nums数组拼接在一起，使用单调栈计算出每一个元素的下一个最大值，最后再把结果集即result数组resize到原数组大小就可以了。
代码如下：
// 版本一
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
// 拼接一个新的nums
vector<int> nums1(nums.begin(), nums.end());
nums.insert(nums.end(), nums1.begin(), nums1.end());
// 用新的nums大小来初始化result
vector<int> result(nums.size(), -1);
if (nums.size() == 0) return result;
// 开始单调栈
stack<int> st;
st.push(0);
for (int i = 1; i < nums.size(); i++) {
if (nums[i] < nums[st.top()]) st.push(i);
else if (nums[i] == nums[st.top()]) st.push(i);
else {
while (!st.empty() && nums[i] > nums[st.top()]) {
result[st.top()] = nums[i];
st.pop();
}
st.push(i);
}
}
// 最后再把结果集即result数组resize到原数组大小
result.resize(nums.size() / 2);
return result;
}
};
这种写法确实比较直观，但做了很多无用操作，例如修改了nums数组，而且最后还要把result数组resize回去。
resize倒是不费时间，是O(1)的操作，但扩充nums数组相当于多了一个O(n)的操作。
其实也可以不扩充nums，而是在遍历的过程中模拟走了两边nums。
代码如下：
// 版本二
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> result(nums.size(), -1);
if (nums.size() == 0) return result;
stack<int> st;
st.push(0);
for (int i = 1; i < nums.size() * 2; i++) {
// 模拟遍历两边nums，注意一下都是用i % nums.size()来操作
if (nums[i % nums.size()] < nums[st.top()]) st.push(i % nums.size());
else if (nums[i % nums.size()] == nums[st.top()]) st.push(i % nums.size());
else {
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;
}
};然后继续看：42. 接雨水 - 力扣（LeetCode）
本题暴力解法也是也是使用双指针。
首先要明确，要按照行来计算，还是按照列来计算。
按照列来计算，比较容易理解，接下来看一下按照列如何计算。
首先，如果按照列来计算的话，宽度一定是1了，我们再把每一列的雨水的高度求出来就可以了。
可以看出每一列雨水的高度，取决于，该列 左侧最高的柱子和右侧最高的柱子中最矮的那个柱子的高度。
一样的方法，只要从头遍历一遍所有的列，然后求出每一列雨水的体积，相加之后就是总雨水的体积了。
首先从头遍历所有的列，并且要注意第一个柱子和最后一个柱子不接雨水，代码如下：
for (int i = 0; i < height.size(); i++) {
// 第一个柱子和最后一个柱子不接雨水
if (i == 0 || i == height.size() - 1) continue;
}
在for循环中求左右两边最高柱子，代码如下：
int rHeight = height[i]; // 记录右边柱子的最高高度
int lHeight = height[i]; // 记录左边柱子的最高高度
for (int r = i + 1; r < height.size(); r++) {
if (height[r] > rHeight) rHeight = height[r];
}
for (int l = i - 1; l >= 0; l--) {
if (height[l] > lHeight) lHeight = height[l];
}
最后，计算该列的雨水高度，代码如下：
int h = min(lHeight, rHeight) - height[i];
if (h > 0) sum += h; // 注意只有h大于零的时候，在统计到总和中
整体代码如下：
class Solution {
public:
int trap(vector<int>& height) {
int sum = 0;
for (int i = 0; i < height.size(); i++) {
// 第一个柱子和最后一个柱子不接雨水
if (i == 0 || i == height.size() - 1) continue;
int rHeight = height[i]; // 记录右边柱子的最高高度
int lHeight = height[i]; // 记录左边柱子的最高高度
for (int r = i + 1; r < height.size(); r++) {
if (height[r] > rHeight) rHeight = height[r];
}
for (int l = i - 1; l >= 0; l--) {
if (height[l] > lHeight) lHeight = height[l];
}
int h = min(lHeight, rHeight) - height[i];
if (h > 0) sum += h;
}
return sum;
}
};接雨水这道题目，我们正需要寻找一个元素，右边最大元素以及左边最大元素，来计算雨水面积。
#准备工作
那么本题使用单调栈有如下几个问题：
- 首先单调栈是按照行方向来计算雨水，如图：
知道这一点，后面的就可以理解了。
- 使用单调栈内元素的顺序
从大到小还是从小到大呢？
从栈头（元素从栈头弹出）到栈底的顺序应该是从小到大的顺序。
因为一旦发现添加的柱子高度大于栈头元素了，此时就出现凹槽了，栈头元素就是凹槽底部的柱子，栈头第二个元素就是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子。
如图：
关于单调栈的顺序给大家一个总结： 739. 每日温度 (opens new window)中求一个元素右边第一个更大元素，单调栈就是递增的，84.柱状图中最大的矩形 (opens new window)求一个元素右边第一个更小元素，单调栈就是递减的。
- 遇到相同高度的柱子怎么办。
遇到相同的元素，更新栈内下标，就是将栈里元素（旧下标）弹出，将新元素（新下标）加入栈中。
例如 5 5 1 3 这种情况。如果添加第二个5的时候就应该将第一个5的下标弹出，把第二个5添加到栈中。
因为要求宽度的时候 如果遇到相同高度的柱子，需要使用最右边的柱子来计算宽度。
如图所示：
- 栈里要保存什么数值
使用单调栈，也是通过 长 * 宽 来计算雨水面积的。
长就是通过柱子的高度来计算，宽是通过柱子之间的下标来计算，
那么栈里有没有必要存一个pair<int, int>类型的元素，保存柱子的高度和下标呢。
其实不用，栈里就存放下标就行，想要知道对应的高度，通过height[stack.top()] 就知道弹出的下标对应的高度了。
所以栈的定义如下：
stack<int> st; // 存着下标，计算的时候用下标对应的柱子高度
明确了如上几点，我们再来看处理逻辑。
#单调栈处理逻辑
以下逻辑主要就是三种情况
- 情况一：当前遍历的元素（柱子）高度小于栈顶元素的高度 height[i] < height[st.top()]
- 情况二：当前遍历的元素（柱子）高度等于栈顶元素的高度 height[i] == height[st.top()]
- 情况三：当前遍历的元素（柱子）高度大于栈顶元素的高度 height[i] > height[st.top()]
先将下标0的柱子加入到栈中，st.push(0);。 栈中存放我们遍历过的元素，所以先将下标0加进来。
然后开始从下标1开始遍历所有的柱子，for (int i = 1; i < height.size(); i++)。
如果当前遍历的元素（柱子）高度小于栈顶元素的高度，就把这个元素加入栈中，因为栈里本来就要保持从小到大的顺序（从栈头到栈底）。
代码如下：
if (height[i] < height[st.top()]) st.push(i);
如果当前遍历的元素（柱子）高度等于栈顶元素的高度，要跟更新栈顶元素，因为遇到相相同高度的柱子，需要使用最右边的柱子来计算宽度。
代码如下：
if (height[i] == height[st.top()]) { // 例如 5 5 1 7 这种情况
st.pop();
st.push(i);
}
如果当前遍历的元素（柱子）高度大于栈顶元素的高度，此时就出现凹槽了，如图所示：
取栈顶元素，将栈顶元素弹出，这个就是凹槽的底部，也就是中间位置，下标记为mid，对应的高度为height[mid]（就是图中的高度1）。
此时的栈顶元素st.top()，就是凹槽的左边位置，下标为st.top()，对应的高度为height[st.top()]（就是图中的高度2）。
当前遍历的元素i，就是凹槽右边的位置，下标为i，对应的高度为height[i]（就是图中的高度3）。
此时大家应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的元素，三个元素来接水！
那么雨水高度是 min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度，代码为：int h = min(height[st.top()], height[i]) - height[mid];
雨水的宽度是 凹槽右边的下标 - 凹槽左边的下标 - 1（因为只求中间宽度），代码为：int w = i - st.top() - 1 ;
当前凹槽雨水的体积就是：h * w。
求当前凹槽雨水的体积代码如下：
while (!st.empty() && height[i] > height[st.top()]) { // 注意这里是while，持续跟新栈顶元素
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;
}
}
关键部分讲完了，整体代码如下：
class Solution {
public:
int trap(vector<int>& height) {
if (height.size() <= 2) return 0; // 可以不加
stack<int> st; // 存着下标，计算的时候用下标对应的柱子高度
st.push(0);
int sum = 0;
for (int i = 1; i < height.size(); i++) {
if (height[i] < height[st.top()]) { // 情况一
st.push(i);
} if (height[i] == height[st.top()]) { // 情况二
st.pop(); // 其实这一句可以不加，效果是一样的，但处理相同的情况的思路却变了。
st.push(i);
} else { // 情况三
while (!st.empty() && height[i] > height[st.top()]) { // 注意这里是while
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;
}
};接着看最后一题：84. 柱状图中最大的矩形 - 力扣（LeetCode）
暴力解法
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int sum = 0;
for (int i = 0; i < heights.size(); i++) {
int left = i;
int right = i;
for (; left >= 0; left--) {
if (heights[left] < heights[i]) break;
}
for (; right < heights.size(); right++) {
if (heights[right] < heights[i]) break;
}
int w = right - left - 1;
int h = heights[i];
sum = max(sum, w * h);
}
return sum;
}
};双指针解法
本题双指针的写法整体思路和42. 接雨水 (opens new window)是一致的，但要比42. 接雨水 (opens new window)难一些。
难就难在本题要记录记录每个柱子 左边第一个小于该柱子的下标，而不是左边第一个小于该柱子的高度。
所以需要循环查找，也就是下面在寻找的过程中使用了while。
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
vector<int> minLeftIndex(heights.size());
vector<int> minRightIndex(heights.size());
int size = heights.size();
// 记录每个柱子 左边第一个小于该柱子的下标
minLeftIndex[0] = -1; // 注意这里初始化，防止下面while死循环
for (int i = 1; i < size; i++) {
int t = i - 1;
// 这里不是用if，而是不断向左寻找的过程
while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];
minLeftIndex[i] = t;
}
// 记录每个柱子 右边第一个小于该柱子的下标
minRightIndex[size - 1] = size; // 注意这里初始化，防止下面while死循环
for (int i = size - 2; i >= 0; i--) {
int t = i + 1;
// 这里不是用if，而是不断向右寻找的过程
while (t < size && heights[t] >= heights[i]) t = minRightIndex[t];
minRightIndex[i] = t;
}
// 求和
int result = 0;
for (int i = 0; i < size; i++) {
int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);
result = max(sum, result);
}
return result;
}
};单调栈
本地单调栈的解法和接雨水的题目是遥相呼应的。
为什么这么说呢，上一题是找每个柱子左右两边第一个大于该柱子高度的柱子，而本题是找每个柱子左右两边第一个小于该柱子的柱子。
这里就涉及到了单调栈很重要的性质，就是单调栈里的顺序，是从小到大还是从大到小。
因为本题是要找每个柱子左右两边第一个小于该柱子的柱子，所以从栈头（元素从栈头弹出）到栈底的顺序应该是从大到小的顺序！
只有栈里从大到小的顺序，才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子。
所以本题单调栈的顺序正好与接雨水反过来。
此时大家应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的三个元素组成了要求最大面积的高度和宽度
理解这一点，对单调栈就掌握的比较到位了。
主要就是分析清楚如下三种情况：
- 情况一：当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况
- 情况二：当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况
- 情况三：当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况
C++代码如下：
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int result = 0;
stack<int> st;
heights.insert(heights.begin(), 0); // 数组头部加入元素0
heights.push_back(0); // 数组尾部加入元素0
st.push(0);
// 第一个元素已经入栈，从下标1开始
for (int i = 1; i < heights.size(); i++) {
if (heights[i] > heights[st.top()]) { // 情况一
st.push(i);
} else if (heights[i] == heights[st.top()]) { // 情况二
st.pop(); // 这个可以加，可以不加，效果一样，思路不同
st.push(i);
} else { // 情况三
while (!st.empty() && heights[i] < heights[st.top()]) { // 注意是while
int mid = st.top();
st.pop();
if (!st.empty()) {
int left = st.top();
int right = i;
int w = right - left - 1;
int h = heights[mid];
result = max(result, w * h);
}
}
st.push(i);
}
}
return result;
}
};