LeetCode——1717. 删除子字符串的最大得分

通过万岁！！！

• 题目：给你一个字符串和两个分数x、y，其中x表示删除“ab”的得分，y表示删除“ba”的得分。然后让你看下最后的最大得分是多少。
• 思路：最开始我也没太有思路，想到了贪心。但是没太想好怎么处理。后面看了下Related Topics，有贪心和栈，坚定了我的思路。这个其实就是两次括号匹配，匹配上了就有得分，然后加上贪心。首先就是要看ab还是ba的分数大。下面的都按照ab大，那我们优先处理ab。我们每次都往栈中添加元素，如果栈顶元素为a，并且下一个元素是b，则a出栈，处理分数即可，这样就把ab处理完了。然后栈内部元素就是剩下的了。同样的道理处理下ba就好了。但是这个方案最后的效果不太好。我最开始一直考虑ab用了以后，会不会影响ba，会不会其他的替换规则会更好。然后写了几个例子，发现没啥影响的，因为他们两个是相反的。
• 技巧：贪心、栈

java代码

class Solution {
    public int maximumGain(String s, int x, int y) {
        if (x > y) {
            return handle(s, 'a', 'b', x, y);
        } else {
            return handle(s, 'b', 'a', y, x);
        }
    }

    public int handle(String s, char first, char second, int max, int min) {
        int ret = 0;
        Stack<Character> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            // 先处理大的组合
            if (!stack.isEmpty() && first == stack.peek() && second == s.charAt(i)) {
                stack.pop();
                ret += max;
            } else {
                stack.push(s.charAt(i));
            }
        }
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        sb = sb.reverse();
        for (int i = 0; i < sb.length(); i++) {
            // 再处理小的组合
            if (!stack.isEmpty() && second == stack.peek() && first == sb.charAt(i)) {
                stack.pop();
                ret += min;
            } else {
                stack.push(sb.charAt(i));
            }
        }
        return ret;
    }
}

• 总结：题目还是挺有意思的，首先就是要将ab和ba统一起来，也就是maximumGain中的处理。还有就是，注意这里的reverse，因为我们通过栈中拿到的元素是反了的。时间复杂度和空间复杂度不太好，先通过万岁吧。