stack(leetcode练习题)

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();
    }
};