字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

提示：

• 1 <= s.length <= 30

• s 由小写英文字母、数字和方括号 '[]' 组成

• s 保证是一个 有效 的输入。

• s 中所有整数的取值范围为 [1, 300] 

解题思路

栈数据结构

该算法使用栈数据结构来处理嵌套的重复模式，主要思想如下：

1. 遍历字符：逐个处理输入字符串的每个字符。

2. 四种情况处理：

   • 字母字符：直接添加到当前字符串构建器(sb)中。

   • 数字字符：累积计算重复次数(multi)，处理多位数字的情况。

   • 左括号'['：将当前字符串和重复次数压入栈，并重置这些变量。

   • 右括号']'：弹出栈中的重复次数和前一个字符串，进行字符串重复操作，并与之前的结果拼接。

class Solution {
    public String decodeString(String s) {
        Stack stack = new Stack();
        char[] chars = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        Integer multi = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] >= 'a' && chars[i] <= 'z') {
                sb.append(chars[i]);
            }
            if (chars[i] >= '0' && chars[i] <= '9') {
                Integer tempInt = Integer.valueOf(String.valueOf(chars[i]));
                multi = (multi * 10) + tempInt;
            }
            if (chars[i] == '[') {
                stack.push(sb.toString());
                sb.setLength(0);
                stack.push(multi);
                multi = 0;
            }
            if (chars[i] == ']') {
                Integer tempMulti = (Integer) stack.pop();
                String tempStr = sb.toString();
                while (tempMulti > 1) {
                    sb.append(tempStr);
                    tempMulti--;
                }

                String stackStr = (String) stack.pop();
                sb.insert(0, stackStr);

            }
        }
        return sb.toString();
    }
}

递归法

通过递归模拟栈的操作，利用函数调用处理嵌套结构。每次遇到 [ 开启新递归层级，遇到 ] 结束当前层级并返回结果。关键变量如下：

1. 静态索引 i：全局跟踪字符处理位置（需注意线程安全问题）

2. preMulti：当前递归层需要重复的次数（由上一层传入）

3. multi：当前累积的数字值（用于遇到 [ 时传给下一层）

注意，decodeString 会重置i = 0 是因为 LeetCode 执行测试用例的时候，如果代码遇到 static变量，是不会重置值的，所以我们人工重置 i 的值。

class Solution {

    private static int i = 0;

    public String decodeString(String s) {
        char[] arr = s.toCharArray();
        String result = doDecodeString(arr, 0);
        i = 0;
        return result;
    }

    public String doDecodeString(char[] arr, int preMulti) {
        int multi = 0;
        StringBuilder sb = new StringBuilder();
        while (i < arr.length) {
            char a = arr[i];
            if (a >= '0' && a <= '9') {
                multi = Integer.parseInt(String.valueOf(a)) + multi * 10;
            } else if (a == '[') {
                i++;
                sb.append(doDecodeString(arr, multi));
                multi = 0;
            } else if (a >= 'a' && a <= 'z') {
                sb.append(a);
            } else if (a == ']') {
                String s = sb.toString();
                while (preMulti-- > 1) {
                    sb.append(s);
                }
                return sb.toString();
            }
            i++;
        }
        return sb.toString();
    }
}

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length

• 1 <= n <= 2 * 104

• 0 <= height[i] <= 105

解题思路

这道题是 盛最多水的容器 的升级版问题，解决的核心还是 "水桶短板效应" ：每个位置能接的雨水量，取决于它左右两侧最高柱子中较矮的那一根。

暴力解法

核心思想：

1. 对每个位置 i 单独处理

2. 向左扫描找到左侧最高柱子

3. 向右扫描找到右侧最高柱子

4. 存水量 = min(左最高, 右最高) - 当前高度

缺点：

• 重复计算严重（每个位置都重新扫描整个数组）

package 接雨水;

class Solution {
	public int trap(int[] height) {
		int count = 0;

		for (int i = 0; i < height.length; i++) {
			int ownHeight = height[i];
			int leftHeight = ownHeight;
			int leftHeightIdx = i;
			int rightHeight = ownHeight;
			int rightHeightIdx = i;
			while (leftHeightIdx >= 0) {
				if (leftHeight < height[leftHeightIdx]) {
					leftHeight = height[leftHeightIdx];
				}
				leftHeightIdx--;
			}

			while (rightHeightIdx < height.length) {
				if (rightHeight < height[rightHeightIdx]) {
					rightHeight = height[rightHeightIdx];
				}
				rightHeightIdx++;
			}

			count += Math.max((Math.min(leftHeight, rightHeight) - height[i]), 0);
		}
		return count;
	}

	public static void main(String[] args) {
		int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
		System.out.println(new Solution().trap(height));
	}
}

双指针法

核心思想：

1. 使用左右指针从两端向中间扫描

2. 动态维护左右两侧遇到的最大值：

   • leftMax：从左侧到当前位置的最大值

   • rightMax：从右侧到当前位置的最大值

3. 关键策略：总是移动较矮一侧的指针

   • 当 height[left] < height[right] 时，计算左指针位置的存水（左最高 - 当前高度）并移动左指针

   • 当 height[right] <= height[left] 时，计算右指针位置的存水（右最高 - 当前高度）并移动右指针

优势：

1. 避免重复计算：动态维护最大值，无需反复扫描

2. 全面覆盖：每个位置都会被左指针或右指针处理到

class Solution {
	public int trap(int[] height) {
		int count = 0;
		int leftHeightIdx = 0;
		int leftHeight = height[leftHeightIdx];
		int rightHeightIdx = height.length - 1;
		int rightHeight = height[rightHeightIdx];

		while (leftHeightIdx < rightHeightIdx) {
			if (height[leftHeightIdx] < height[rightHeightIdx]) {
				if (height[leftHeightIdx] > leftHeight) {
					leftHeight = height[leftHeightIdx];
				}
				count += Math.max((leftHeight - height[leftHeightIdx]), 0);
				leftHeightIdx++;
			} else {
				if (height[rightHeightIdx] > rightHeight) {
					rightHeight = height[rightHeightIdx];
				}
				count += Math.max((rightHeight - height[rightHeightIdx]), 0);
				rightHeightIdx--;
			}
		}
		return count;
	}
}