题目描述

  给你一个包含若干星号 * 的字符串 s 。在一步操作中，你可以：选中 s 中的一个星号。移除星号 左侧 最近的那个 非星号 字符，并移除该星号自身。返回移除 所有 星号之后的字符串。注意：生成的输入保证总是可以执行题面中描述的操作。可以证明结果字符串是唯一的。

解析

  虽然这题是栈的类别，但实际上不需要使用栈，而且不是很难。由于确定前面一定有可以删除的，所以可以直接从后往前遍历，会更快一点。

public String removeStars(String s) {
        StringBuilder res = new StringBuilder();
        int starCount = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            if (c == '*') {
                starCount++;
            } else if (starCount > 0) {
                starCount--;
            } else {
                res.append(c);
            }
        }
        return res.reverse().toString();
    }

把栈的解法也贴出来：

public String removeStars(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '*') {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else {
                stack.push(c);
            }
        }

        StringBuilder stringBuilder = new StringBuilder();
        while (!stack.isEmpty()) {
            stringBuilder.append(stack.pop());
        }
        stringBuilder.reverse();

        return stringBuilder.toString();
    }