栈
在本文中，我将介绍一下栈的基本用法以及单调栈相关的知识
Leetcode1047.删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 s 上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
eg.输入：“abbaca” 输出：“ca”
此题比较明显可以用栈数据结构来解决，对于每个字符依次压入栈，并判断和栈顶的元素是否相等，相等则pop。需要注意的一点是字符串已经内置了栈的操作，vector也是。
string removeDuplicates(string s)
{
string stk;
for(char x:s)
{
if(!stk.empty() &&x==stk.back())
{
stk.pop_back();
}
else
{
stk.push_back(x);
}
}
return stk;
}leetcode20.有效的括号
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：左括号必须用相同类型的右括号闭合;左括号必须以正确的顺序闭合;每个右括号都有一个对应的相同类型的左括号。
这个是一道经典的可以用栈解决的问题，后来的括号是先被匹配的，符合栈的后进先出的特点。
bool isValid(string s){
int n=s.size();
if(n%2==1) return false;
unordered_map<int,int>pairs{
{')','('},
{']','['},
{'}','{'}
};
stack<char>stk;
for(char x:s)
{
if(pairs.count(x))
{
if(stk.empty() ||stk.top()!=pairs[x])
{
return false;
}
stk.pop();
}
else
{
stk.push(x);
}
}
return s.empty();
}借助哈希表，用右括号来判断是应该出栈还是入栈
leetcode394.字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[ encoded_string ]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
eg.输入：s=”3[ a ]2[ bc ]”;输出：“aaabcbc”。 输入：s=”3[ a2[ c ]]”; 输出：”accaccacc”
题目分析
- 对于一对括号内重复的字符串，我们需要知道这个子串需要重复多少次，并且还要将这个子串从原来的字符串中提取出来。
- 依次从第一个字符开始遍历，遇到左括号就将左括号前的数字和左括号前的字符长度压入栈中(用哈希表)，遇到右括号，可以得到有括号前的字符长度，这样就能将子串提取出来，并对这串子串重复操作。
代码部分
string decodeString(string s)
{
stack<pair<int,int>> stk;
string ans;
int count=0;
for(char x:s)
{
if(isdigit(x))
{
count=count*10+x-'0';
}
else if(x=='[')
{
stk.push({count,ans.size()});
count=0;
}
else if(isalpha(x))
{
ans+=x;
}
else if(x==']')
{
int n=ans.size();
string substr=ans.substr(stk.top().second,n-stk.top().second);
for(int i=0;i<stk.top().first-1;i++)
{
ans+=substr;
}
stk.pop();
}
}
return ans;
}Leetcode32最长有小括号
给你一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
eg. 输入：” （ ））”;输出：2。 输入：”）（）（））” ;输出：4
题目分析
子串一定是以”（”开始，以”）”结束的。遇到”（”就push，遇到”）”就pop,并记录一下最大长度。
代码部分
int longestValidParentheses(string s)
{
int maxlen=0;
stack<int>stk;
stk.push(-1);
for(int i=0;i<s.length();i++)
{
if(s[i]=='(')
{
stk.push(i);
}
else
{
stk.pop();
if(stk.empty())
{
stk.push(i);
}
maxlen=max(maxlen,i-stk.top());
}
}
return maxlen;
}一开始的时候将-1压入栈中，是为了可以与“）….”类型的字符配对。并且配对后，如果栈为空，继续将”）”的索引压入栈中，方便后续的计算。
验证栈序列
给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。
eg.输入：pushed=[1,2,3,4,5],poped=[4,5,3,2,1] 输出：true。
pushed=[1,2,3,4,5],poped=[4,3,5,1,2] 输出：false。 1不能在2之前弹出。
bool validateStackSequences(vector<int>& pushed, vector<int>& poped)
{
stack<int>stk;
int j=0;
for(int i=0;i<poped.size();i++)
{
while(stk.empty() || stk.top()!=poped[i])
{
if(j<poped.size())
{
stk.push(pushed[j]);
j++;
}
else
{
break;
}
}
if(stk.top()==poped[i])
{
stk.pop();
}
else
{
return false;
}
}
return true;
}leetcode739 每日温度
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
eg.输入：temperatures=[ 73,74,75,71,69,72,76,73];输出：[ 1,1,4,2,1,1,0,0]
题目分析
- 此题用到的思想就是单调栈，从最后一个元素开始遍历，判断其和栈顶元素的大小，如果小于则直接将其压入栈中，否则，将栈顶元素弹出，直到该元素是大于栈顶元素(或者栈为空)。
- 栈中的每个元素需要包含数值的大小和序号。
vector<int> dailyTemperatures(vector<int>& temperatures)
{
stack<pair<int,int>>stk;
int n=temperatures.size();
vector<int>ans(n,0);
for(int i=n-1;i>=0;i--)
{
while(!stk.empty() && stk.top().second<=temperatures[i])
{
stk.pop();
}
ans[i]=stk.empty()? 0:stk.top().first-i;
cout<<ans[i]<<endl;
stk.push({i,temperatures[i]});
}
return ans;
}leetcode496下一个更大元素
nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
eg.输入：nums1=[ 4,1,2],nums2=[ 1,3,4,2] 输出：[ -1,3,-1]
题目分析
首先可以用单调栈的方法把nums[ 2]中所有元素对应的下一个更大的元素求出来，那该怎么存储这些结果，方便nums1中的查找呢？答案是哈希表。
vector<int>nextGreaterElement(vector<int>&nums1,vector<int>&nums2)
{
unordered_map<int,int> hashmap;
stack<int>stk;
int n =nums2.size();
vector<int>ans(nums1.size(),0);
for(int i=n-1;i>=0;i--)
{
while(!stk.empty() && nums2[i]>=stk.top())
{
stk.pop();
}
hashmap[nums2[i]]=stk.empty()?-1:stk.top();
stk.push(nums2[i]);
}
for(int i=0;i<nums1.size();i++)
{
ans[i]=hashmap[nums1[i]];
}
return ans;
}得到的结果用hashmap[nums2[ i]]表示，然后用hashmao[ nums1[ i]]来找到对应的结果。
leetcode503下一个更大元素2
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
eg.输入:nums=[ 1,2,1],输出：[ 2,-1 ,2]
题目分析
这个题目主要多了循环这个特点，意味着可以从头再找。所以我打算先把整个数组逆序压入栈中，然后再用单调栈的方法。
vector<int> nextGreaterElements(vector<int>&nums)
{
vector<int>ans(nums.size());
stack<int>stk;
for(int i=nums.size();i>=0;i--)
{
stk.push(nums[i]);
}
for(int i=nums.size()-1;i>=0;i--)
{
while(!stk.empty() && nums[i]>=stk.top())
{
stk.pop();
}
ans[i]=stk.empty()?-1:stk.top();
stk.push(nums[i]);
}
return ans;
}