在题目的要求中，存在先进后出（即在前面的数据需要遍历到后面的某一数据时才能确定计算值）单调栈在一部分解题场景中避免了暴力解法的高时间复杂度问题，但是在做题过程中视情况而定，有些题目的最优解不一定使用单调栈，需要灵活解题，多思考一下或许有更加简便的算法和逻辑。
LeetCode 经典题目：
1. 「力扣」第84： 柱状图中最大的矩形
算法思想：
创建一个保存元素下标的 整形栈，遍历数组依次入栈：
- 当前值比栈顶元素大时，入栈当前元素下标
- 当前值比栈顶元素小时，说明栈顶元素此时可以判断面积了->出栈
- 需要注意的是，出栈后的栈顶元素判断区间（宽）= 当前数组的的下标i与现在的栈顶元素的距离-1
- 出栈的栈顶元素对应的数组值为（高）
- 在首位添加哨兵（值为0的元素），在下标处理计算、首尾判断时无需特殊处理（类似链表头结点删除），更为简便
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int>s;
int len = heights.size() + 2;
vector<int>h2;
h2.push_back(0);//头哨兵
for(int i = 0;i< heights.size(); i++)
{
h2.push_back(heights[i]);//复制中间元素
}
h2.push_back(0);//尾哨兵
//转换新的数组（首尾哨兵结点）
int area = 0;
s.push(0);
//头哨兵入栈，便于计算间距
for (int i = 1; i < h2.size(); i++)
{
if (h2[i] >= h2[s.top()])
s.push(i);
else
{
while (h2[i] < h2[s.top()])
{
int tmp = s.top();
s.pop();
int a = (i - s.top() - 1) * h2[tmp];
area = area < a ? a : area;
}
i--;
//当前的i 作用于出栈计算之前不能确定的面积，
//但当所有符合条件的下标出栈后，i下标对应的栈顶元素也重新对应，
//应当再次对i是否入栈做判断，i--再给一次机会
}
}
return area;
}
};2. 「力扣」第42题：接雨水
算法思想：
- 用两侧的高墙才能将水围住，只需要找到比当前墙更高或一样高的另一面墙才能计算出之间的水量，（间距*墙高-中间的矮墙），得到这一区间的水量，下标从后一面墙继续向结尾遍历
- 需要注意的是上面的设想存在一种情况，当前面的墙高于后面的所有墙，则无法判断，所以在确认以第一面墙的标准的时候，需要向后寻找最高的墙是否存在高于当前的墙，如果没有，则将第一面墙的高度降低为后续最高墙一致的高度，确保算法无遗漏
- 具体实现：
-
- 创建栈保存元素下标，当后续元素小于栈顶元素时（中间低墙，直接跳过）
- 遍历的元素大于或等于栈顶元素时，此时可以确定中间的积水区域，当前（下标i - 栈顶元素下标）*栈顶元素的数值-区间中间的元素”低墙 “，不断累加
- 计算积水区域结束后， 后一面墙若不是最后一个元素，则入栈（并作最大值判断）
算法思想2：
数组从左向右计算该元素后可以累计的积水量，再从右向左重复判断，两次的结果取最小值累加为结果
class Solution {
public:
int trap(vector<int>& height) {
stack<int>s;
int sum = 0;
s.push(0);
if(height.size()>1)
{
int max = *max_element(height.begin() + s.top() + 1, height.end());
if (height[0] > max)
height[0] = max;
}
for (int i = 1; i < height.size(); i++)
{
if (height[i] >= height[s.top()])
{
sum += (i - s.top() - 1) * height[s.top()];
for (int j = s.top() + 1; j < i; j++)
sum -= height[j];
s.pop();
if(i!=height.size()-1)
{
s.push(i);
int max0 = *max_element(height.begin() + s.top() + 1, height.end());
if (height[i] > max0)
height[i] = max0;
}
}
}
return sum;
}
};3. 「力扣」第739题：每日温度
算法思想：
创建栈保留数组下标
- 入栈0号下标，用作第一次元素值判断
- 当遍历的元素值大于栈顶元素时，计算间距保存到数组并出栈
- 若遍历元素小于栈顶元素时，入栈，后序遍历过程中才能得到答案
- esay 的实现了
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
vector<int>v(temperatures.size());
stack<int>s;
s.push(0);
int i;
for (i = 1; i < temperatures.size(); i++)
{
if (temperatures[i] > temperatures[s.top()])
{
while (s.size() > 0 && (temperatures[i] > temperatures[s.top()]))
{
v[s.top()] = i - s.top();
s.pop();
}
s.push(i);
}
else
s.push(i);
}
return v;
}
};4. 「力扣」第496题：下一个更大元素
算法思想：
- 将nums2的元素从后向前遍历，顺序入栈，且始终保持栈内元素递减，则栈内元素的下一元素为所求的nums2 的下一更大元素
- 当栈内为空，直接入栈；
- 栈不为空，当前元素大于栈顶元素，出栈，保持栈内顺序递减
- 在保持当前新元素入栈后栈内元素依旧递减的状态（此时新元素未入栈）
-
- 当栈为空，说明nums2不存在下一更大元素
- 当栈不为空，则栈顶为所求的下一更大元素
- 这些所求信息用哈希表存储，key为所求元素，value为下一更大元素
- 在所有信息都保存在哈希表的基础上，只需查询map[key]对应的值返回结果即可
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
//单调栈
vector<int>v(nums1.size(), -1);
unordered_map<int, int>hashmap;
stack<int>s;
for (int i = nums2.size() - 1; i >= 0; i--)
{
if (s.empty()!=1&&nums2[i] > s.top())
{
while (s.empty() != 1 && nums2[i] > s.top())
{
s.pop();
}
}
hashmap[nums2[i]] = s.empty() ? -1 : s.top();
s.push(nums2[i]);
}
for (int i = 0; i < nums1.size(); i++)
{
v[i] = hashmap[nums1[i]];
}
return v;
}
};5. 「力扣」第316题：去除重复字母
class Solution {
public:
string removeDuplicateLetters(string s) {
unordered_map<char, int>map;
unordered_map<char, bool>b;
for (int i = 0; i < s.size(); i++)
{
map[s[i]]++;
b[s[i]] = 0;
}
string s2 = "";
for (auto it=s.begin();it!=s.end();it++ )
{
if (b[*it] == 0)//如果栈内不存在
{
while (!s2.empty() && s2.back() > *it&& map[s2.back()] >0)//如果栈头大于 it
{
b[s2.back()] = 0;
s2.pop_back();
}
s2.push_back(*it);
b[*it] = 1;
}
map[*it]--;//所有it在循环遍历时依次--；与是否入栈无关
}
return s2;
}
};谁说用单调栈解题就一定要用栈stack当容器了？ string不行吗？
算法思想：
这道题解决两个问题：删除重复项、字典序排列！
- 用哈希表unordered_map1<char,int>实现，键值对键存数据，value存次数
- 第二个问题需要结合第一个问题的哈希表实现排列：
哈希表2unordered_map1<char,bool> value 值为0，代表是否当前元素已在栈中，入栈value为1，出栈后改为0；
- 字典序排列：
-
- 当遍历的当前元素不是重复元素时则直接入栈（map1[key]==1时）
- 当遍历的当前元素小于栈顶元素的字典序时，并且栈顶元素为重复元素时：出栈入新元素（!s2.empty() && s2.back() > *it&& map[s2.back()] >0）
- 当遍历到栈内存在的元素时(map2[]==1;)，跳过，因为栈内已经是最优解
- 在每次遍历元素结束后，将该元素的map1计数器--
6. 「力扣」第402题：移掉K位数字
算法思想：
- 从数组开头向后遍历的过程中入栈，必须保持入栈的数据保持递增
- 若后面入栈的数据小于栈内栈顶元素，则出栈直到入栈新数据保持所有数据有序
- 每次出栈则代表删除一个元素，移除的计数器加加
- 若计数器在未遍历完所有数组元素时已经归零，则直接将剩余的数组元素入栈
- 若遍历完所有数组元素后，移除的计数器依然未归零，（因为当前栈内数据保持有序，则栈顶元素为最大值），则移除栈顶元素直至计数器归零
- 此时栈底到栈顶为有序递增，出栈后数据顺序必然颠倒，所以在返回之前将数组元素reverse
- 特殊判断：
-
- 若栈内为空，则返回string “0”
- 若数据头部有0 eg: ”001“ 当删除头部 0，再输出
class Solution {
public:
string removeKdigits(string num, int k) {
stack<int>s;
string s2;
for (int i = 0; i < num.size(); i++)
{
while(!s.empty() && num[i] <s.top()&&k>0)
{
s.pop();
k--;
}
s.push(num[i]);
}
//未删完从尾巴删
while (k > 0)
{
s.pop();
k--;
}
//判空返回0
if (s.empty())
{
s2.push_back('0');
return s2;
}
while (!s.empty())
{
s2.push_back(s.top());
s.pop();
}
//栈底含有0
while (s2.back() == '0'&&s2.size()>1)
s2.pop_back();
reverse(s2.begin(), s2.end());
return s2;
}
};7. 「力扣」第581题：最短无序连续子数组
这道题的解题并没有用到栈，但是需要记忆该题的算法思想：
谁说一定要用单调栈解题？
- 寻找中间的子串使得整段数据有序
- 将原数据复制一份并排序，对比左右两侧最大的相等区间，中间部分即为所求
- 这道题虽然也出现在单调栈的题目集合中，但是使用单调栈的方法不一定简单易实现，需要我们灵活判断使用
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
//排序后，比对原数组，得到左边界与右边界
vector<int>v = nums;
sort(v.begin(), v.end());
int i, j;
for (i = 0, j = nums.size() - 1; i < j; )
{
if (nums[i] == v[i])i++;
if (nums[j] == v[j])j--;
else if (nums[i] != v[i] && nums[j] != v[j])
break;
}
if (i>=j)
return 0;
return j-i+1;
}
};总结：
- 将不能判断的元素下标入栈，直至可以判断时出栈；
- 注意利用元素的下标区间的作用
- 是否需要首位哨兵结点，避免多余的判断
题目也许有简单算法、实现方法，也许我们用了另一种很艰难的算法实现了，但是也并不能说明这道题我们解的很好，要尝试多练习、多思考，不断寻找最优解