一、1190. 反转每对括号间的子串
给出一个字符串 s（仅含有小写英文字母和括号）。 请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。 注意，您的结果中 不应 包含任何括号。 示例 1： 输入：s = "(abcd)" 输出："dcba" 示例 2： 输入：s = "(u(love)i)" 输出："iloveu" 解释：先反转子字符串 "love" ，然后反转整个字符串。
思路：遇到( 还有字符直接入栈，遇到第一个)，进行出战操作并进行反转字符串操作
class Solution { public String reverseParentheses(String s) { Stack<String> stack=new Stack<String>(); StringBuilder str = new StringBuilder(); for(char c : s.toCharArray()){ if(c=='('){ stack.push(str.toString()); str = new StringBuilder(); }else if(c==')'){ str = new StringBuilder(stack.pop() + str.reverse()); }else{ str.append(c); } } return str.toString(); } }
二、单调栈 接雨水
给定 n 个非负整数表示每个宽度为 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 个单位的雨水（蓝色部分表示雨水）。
这倒题还是一个没有想出来的状态只是单单实现了暴力的解法，看到官网上有很多方法。
暴力解法。
思路遍历每一个数组下标，并向左和向右进行遍历，将两边最大高度的较小值减去当前高度的值。
class Solution { public int trap(int[] height) { int ans = 0; int size = height.length; for (int i = 1; i < size - 1; i++) { int max_left = 0, max_right = 0; for (int j = i; j >= 0; j--) { max_left = Math.max(max_left, height[j]); } for (int j = i; j < size; j++) { max_right = Math.max(max_right, height[j]); } ans += Math.min(max_left, max_right) - height[i]; } return ans; } }
这样时间复杂赴会很高，双层For循环，On2
