力扣 20. 有效的括号，496. 下一个更大元素 I，739. 每日温度，856. 括号的分数，32. 最长有效括号

20. 有效的括号

题目

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

AC代码

class Solution {
public:bool isValid(string s) {map<char,int>m{{'(',1},{'[',2},{'{',3},{')',4},{']',5},{'}',6}};// 设置权重，便于比较有效符号对stack<int>st;// 储存 符号对 的 前符号bool ans=true;for(auto c : s){int t=m[c];if(t>=1&&t<=3)  st.push(t);else if(!st.empty()&&t==st.top()+3) st.pop();else // 出现无效符号{ans=false;break;}}if(!st.empty())ans=false;// 最后有多余的前符号，则字符串无效return ans;}
};

496. 下一个更大元素 I

题目

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

AC代码

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {map<int,int>mp;for(int i=0;i<nums2.size();i++)    mp[nums2[i]]=i+1;// 标记 nums2 的下标vector<int>ans; // 储存答案for(int i=0;i<nums1.size();i++){int x=nums1[i],y=mp[nums1[i]];int f=0;for(int j=y;j<nums2.size();j++)// 寻找 右边 较大值{if(nums2[j]>x){f=1;ans.push_back(nums2[j]);break;}}if(f==0)ans.push_back(-1);}return ans;}
};

739. 每日温度

题目描述

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

AC代码

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n=temperatures.size();vector<int> ans(n);stack<int>q;for(int i=0;i<n;i++){while(!q.empty()&&temperatures[i]>temperatures[q.top()])// 找到第 i 位左边的第一个比第 i 位数的数{int t=q.top();ans[t]=i-t;// 储存按要求的答案q.pop();}q.push(i);}return  ans;}
}; 

856. 括号的分数

题目

给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：

() 得 1 分。
AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
(A) 得 2 * A 分，其中 A 是平衡括号字符串。

输入

S 是平衡括号字符串，且只含有 ’ ( ’ 和 ’ ) ’ 。

2 <= S.length <= 50

AC代码

class Solution {
public:int scoreOfParentheses(string s) {int ans=0,n=s.size(),t=0;for(int i=0;i<n;i++){if(s[i]=='(')   t++;else    t--;if(s[i]==')'&&s[i-1]=='('){ans+=1<<t; // 加上 2 的符号对数}}return ans;}
};

32. 最长有效括号

题目

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

AC代码

class Solution {
public:int longestValidParentheses(string s) {int ans=0;stack<int>st;st.push(-1);for(int i=0;i<s.size();i++){if(s[i]=='(')    st.push(i);else{st.pop();if(st.empty())st.push(i);elseans=max(ans,i-st.top());// 匹配到完整字符串}}return ans;}
};