LC刷题专题：队列、双端队列、栈

这个专题记录自己刷题过程中遇到的与队列有关的题目

1190. 反转每对括号间的子串

题目链接及描述
https://leetcode.cn/problems/reverse-substrings-between-each-pair-of-parentheses/description/

看到成对的括号，首先联想到的就是使用栈，当遇到“）”时从栈中弹出元素，直至遇到“（”为止，将弹出的字符组成的字符串进行反转操作。普通实现思路按照上面描述。
我进一步思考觉得每次都将单个字符入栈，并且遇到左括号后需要从栈中一个个弹出当前元素并构成字符串，对其进行反转操作，执行反转后需要再次遍历字符串并将其对应元素入栈。这个过程中涉及到大量遍历字符串取字符的操作。
我考虑将栈中存储字符的操作更改为栈中直接存储的就是字符串。 定义字符串cur表示当前尚未入栈的字符串，当遇到右括号“）”时，将当前字符串反转，反转后需要考虑更新当前字符串cur，如果栈顶字符串为左括号“（）”则，此时不需要更新字符串，继续向后遍历，如果当前栈顶字符串不为左括号。则将栈顶字符串弹出并将cur连接在其后组成新的字符串cur。注意细节看代码：

class Solution {
    public String reverseParentheses(String s) {
        Stack<String> st = new Stack<>();
        String cur = "";
        for(char ch : s.toCharArray()){
            if(ch == '('){
                // 遇到右括号，需要将右括号前面的内容入栈，并且需要将右括号入栈
                // 右括号入栈主要是为了和左括号匹配，防止出现多个括号中间没有内容导致不匹配的反转
                // "((eqk((h))))"
                if(cur != ""){
                    st.push(cur);
                    cur = "";
                }
                st.push('(' + "");
            }else if(ch == ')'){
                // 遇到左括号，首先将对应的右括号从栈中弹出，随后反转字符串。
                if(!st.isEmpty() && st.peek() == "("){
                    st.pop();
                }
                cur = reverseString(cur);
                // 字符串反转后需要判断当前栈顶元素是否为右括号，如果是，继续操作，不是需要将当前栈顶元素弹出和当前cur共同组成下一个反转字符串
                if(!st.isEmpty() && st.peek() != "("){
                    cur = st.pop() + cur;
                }
            }else{
                cur += ch;
            }
        }
        return cur;
    }
    public String reverseString(String s){
        String ans = "";
        for(int i = 0; i < s.length(); i++){
            ans = s.charAt(i) + ans;
        }
        return ans;
    }
}

649. Dota2 参议院

参考博客连接：https://blog.csdn.net/weixin_45863010/article/details/139611145

735. 小行星碰撞

参考博客链接：https://blog.csdn.net/weixin_45863010/article/details/139513329

901. 股票价格跨度

参考博客链接：https://blog.csdn.net/weixin_45863010/article/details/139250873

原文地址：https://blog.csdn.net/weixin_45863010/article/details/142743931

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！