2021 8.8拼多多笔试第三题解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.nextLine();
		String s = sc.nextLine();
		char[] ch = s.toCharArray();
		System.out.println(Arrays.toString(ch));
		int[] ans = new int[n];
		int p = -1;
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < n; i++) {
			if (ch[i] == '(' || (s.charAt(i) == ')')) {
				p++;
				sb.insert(p, ch[i]);
			} else if (ch[i] == 'L' && p >= 0) {
				if (p >= 0)
					p--;
			} else if (ch[i] == 'R' && p >= 0) {
				if (p < sb.length() - 1)
					p++;
			} else if (ch[i] == 'D') {
				if (p >= 0) {
					sb.deleteCharAt(p);
					p--;
				}
			}
			ans[i] = test(sb);
			System.out.println(sb);
		}
		System.out.println(Arrays.toString(ans));
	}

	static int test(StringBuilder sb) {
		char[] ch = sb.toString().toCharArray();
		Stack<Character> stack = new Stack<Character>();
		int res = 0;
		int maxTop = 0;
		for (char c : ch) {
			if (c == '(') {
				stack.push(c);
				maxTop = Math.max(maxTop, stack.size());
			}
			if (c == ')') {
				res--;
				if (!stack.isEmpty()) {
					stack.pop();
					res++;
				}
			}
		}
		if (stack.isEmpty()&&res==0) {
			return maxTop;
		}
		while (!stack.isEmpty()) {
			stack.pop();
			res--;
		}
		return res;
	}
}