STL用法总结
关于stack的知识,可以看点击查看上面的博客,以下题目全在leetcode
32 最长有效括号
思路
“(()”
“()(()”
“(()(((()”
最开始写的,总会有一些样例过不了,没考虑全,后来看题解上的方法,将下标压入栈中,用右括号的下标减去栈顶下标,就是有效长度。看来那位讲题同学说的,先忽略最长是有道理。不然只顾着最长,反而无法得到正确的有效长度。
代码
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> k;
int l=0,r=0,ans=0 ;
k.push(-1);//初始化,压栈
for(int i=0;i<s.size();i++)
{
if(s[i]=='(')
{
k.push(i);
}
else
{
k.pop();
if(k.empty())
k.push(i);
else
ans=max(ans,i-k.top());
}
}
return ans;
}
};
496 下一个最大元素
思路
运用栈,可以很好解决。要找下一个最大元素。可以将数组倒着入栈。如果数字比栈顶小就压入,否则,将栈顶删除直到,比栈顶小或这栈为空。此时栈顶就是答案,为空则标记为-1;
代码
class Solution {
public:int a[10050];
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
stack<int> k;
vector<int> v;
for(int i=nums2.size()-1;i>=0;i--)
{
while(!k.empty()&&nums2[i]>=k.top())
{
k.pop();
}
if(k.size()==0) a[nums2[i]]=-1;
else a[nums2[i]]=k.top();
k.push(nums2[i]);
}
for(int i=0;i<nums1.size();i++)
v.push_back(a[nums1[i]]);
return v;
}
};
856 括号的分数
思路
一个完整的括号,要么是1,要么里边包含其他括号,进行了 *2。所以,可以每遇到一个右括号,进行一次运算,第一次为 1,以后每次乘二,累加到栈顶。遇到左括号,就向栈压入0,重新运算,当遇到右括号,再弹出.
class Solution {
public:
int scoreOfParentheses(string s) {
stack<int> k;
k.push(0);//先推入0,防止k为空
for (int i=0;i<s.size();i++) {
if (s[i] == '(') {
k.push(0);
} else {
int v = k.top();
k.pop();
k.top() += max(2 * v, 1);
}
}
return k.top();
}
};