LeetCode 解题思路 4（Hot 100）

解题思路：

1. 初始化： 判断边界条件，初始化栈并将第一根柱子的索引入栈。
2. 遍历处理： 对于每一个右侧柱子 height[i]，若柱子高度大于栈口索引，保留栈口元素为 mid，随后 peek() 得到 mid 左侧柱子。
3. 计算雨水量： 取左右柱子最小值作为 h，左右索引距离为 w，横向计算雨水量 s 直至栈为空或当前右侧柱子小于栈顶柱子高度。

Java代码：

class Solution {public int trap(int[] height) {if (height.length <= 2) return 0;Stack<Integer> stack = new Stack<>();stack.push(0);int sum = 0;for (int i = 1; i < height.length; i++) {int top = stack.peek();if (height[i] < height[top]) {stack.push(i);} else if (height[i] == height[top]) {stack.push(i);} else {while (!stack.isEmpty() && height[i] > height[top]) {int mid = stack.pop();if (!stack.isEmpty()) {int left = stack.peek();int h = Math.min(height[left], height[i]) - height[mid];int w = i - left - 1;int s = h * w;sum += s;top = stack.peek();}}stack.push(i);}}return sum;}
}

复杂度分析：

• 时间复杂度： 严格 O(n)，每根柱子最多被压入和弹出栈一次。
• 空间复杂度： 在最坏的情况下，栈中可能会存储所有的柱子索引。所以空间复杂度是 O(n)。

解题思路：

1. 使用两个指针： 分别表示当前窗口的起始和结束位置。
2. 使用哈希集合： 存储当前窗口内的字符，以便快速判断是否存在重复字符。
3. 遍历字符串： 若当前字符不在哈希集合中，将其加入集合，并更新最长字串的长度。若当前字符已经在哈希集合中，移动左指针直到窗口不再有重复字符，同时从集合中移除当前字符。

Java代码：

class Solution {public int lengthOfLongestSubstring(String s) {if (s == null || s.length() == 0) return 0;char[] chars = s.toCharArray();Set<Character> set = new HashSet<>();int res = 0; int left = 0;for (int right = 0; right < chars.length; right++) {while (set.contains(chars[right])) {set.remove(chars[left]);left++;}set.add(chars[right]);res = Math.max(res, right - left + 1);}return res;}
}

复杂度分析：

• 时间复杂度： 严格 O(n)，因为每个字符最多被访问两次。
• 空间复杂度： O(min(m, n))，其中 m 是字符集的大小，n 是字符串的长度。