2020 11/05

1021. 删除最外层的括号

题目

思路

计数法

因为本题说S一定是一个有效括号字符串，所以S[0]一定是’(‘;
可以设置两个标识位：

• left：左括号数量
• right：右括号数量

在遍历字符串中，如果left == right 说明，和最外层括号匹配上了，就清空当前的状态。否则就把字符压倒结果后面
例：

(()())
i=0 left=1 right=0 ( ————》 ""
i=1 left=2 right=0 (( ————> "("
i=2 left=2 right=1 (() ————> "()"
i=3 left=3 right=1 (()(  ————> "()("
i=4 left=3 right=2 (()() ————> "()()"
i=5 left=3 right=2 (()())  ————》 匹配上外层

辅助栈法

可以借助栈的特性来实现，过程如下：

• 如果栈是空并且是左括号，压入左括号
• 如果栈不是空并且是左括号，压入左括号，并压入结果字符串
• 如果右括号，弹出栈
  • 如果此时不是空栈，压入结果字符串

(()())

i=0 stack=[(] str=""
i=1 stack=[((] str="("
i=2 stack=[(] str="()"
i=3 stack=[(] str="()("
i=4 stack=[(] str="()()"
i=4 stack=[] str="()()"

实现

计数法

class Solution {
public:
    string removeOuterParentheses(string S) {
        int L = 1;
        int R = 0;
        string ans;
        for (int i=1; i<S.size(); ++i){
            if (S[i] == '(') L++;
            else R++;
            if (R != L) ans.push_back(S[i]);
            else {
               ++i;// 跳过下一个的第一个左括号
               L = 1;
               R = 0; 
            }
        }
        return ans;

    }
};

栈

class Solution {
public:
    string removeOuterParentheses(string S) {
        stack<char> stack;
        string res;
        for (char c : S) {
            // 第一个左括号
            if (stack.empty() && c == '(') {
                stack.push('(');
            // 记录有意义的左括号
            } else if (!stack.empty() && c == '(') {
                stack.push('(');
                res.push_back(c);
            }
            // 记录右括号
            if (c == ')') {
                stack.pop();
                if (!stack.empty()) 
                    res.push_back(c); //弹出一对有意义的数据
            }
        }
        return res;
    }
};

503. 下一个更大元素 II

题目

思路

这题是之前下一个更大元素的变形，可以先看以下之前下一个更大元素的代码
class Solution {
public:
vector nextGreaterElement(vector& nums1, vector& nums2) {
stacks;//临时栈
unordered_mapnum_map; //哈希表
int size = nums1.size();
vectorvec_num;//存储下一个最大值的vector

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int>s;//临时栈
        unordered_map<int,int>num_map; //哈希表
        int size = nums1.size();
        vector<int>vec_num;//存储下一个最大值的vector

        for(int i = 0;i < nums2.size();++i){
            while(!s.empty() && nums2[i]>s.top()){
                num_map[s.top()] = nums2[i];
                s.pop();
            }
            s.push(nums2[i]);
        }

        while(!s.empty()){
            num_map[s.top()] = -1;
            s.pop();
        }

        for(int i = 0;i<size;++i)
            vec_num.push_back(num_map[nums1[i]]);

        return vec_num;
    }
};

规本题则一样但是下一个更大的数是从开头就开始找，而不是那个数后面。

这就类似在一个环形数组里面来寻找下一个更大的元素。这就可以借助取余来解决，思路如下

• 将遍历的长度扩大为原先的2倍数
• 获取值的时候，通过取余，来获得实际上第二段长度的真实位置

实现

vector<int> nextGreaterElements(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n); // 存放结果
    stack<int> s;
    // 假装这个数组长度翻倍了
    for (int i = 2 * n - 1; i >= 0; i--) {
        while (!s.empty() && s.top() <= nums[i % n])
            s.pop();
        res[i % n] = s.empty() ? -1 : s.top();
        s.push(nums[i % n]);
    }
    return res;
}