【算法二十二】 739. 每日温度 42.接雨水
739. 每日温度
单调栈：
class Solution { public int[] dailyTemperatures(int[] temperatures) { int n = temperatures.length; Deque<Integer> stack = new ArrayDeque<>(); int[] ans = new int[n]; for(int i = 0;i<n;i++){ while(!stack.isEmpty() && temperatures[i]>temperatures[stack.peek()]){ int j = stack.pop(); } } } }时间复杂度：O(N)
空间复杂度：O(N)
核心：
遇到“找右边第一个比我大的数”、“找左边第一个比我小的数”
处理“凹”或“凸”的形状：比如接雨水（找凹槽）或者最大矩形面积（找左右边界）
计算“跨度”或“贡献”：某个数在什么范围内是最大的？（比如：子数组最小值之和）
42. 接雨水
双指针：
class Solution { public int trap(int[] height) { int ans = 0; int left = 0; int right = height.length - 1; int preMax = 0; int behMax = 0; while(left < right){ //计算高度包含本高度的原因是,不需要写 if-else 去判断当前柱子是否比最大高度矮 //矮的可以存水，高的不能存水 //代码通过一次减法自动兼容了存水还是不能存水的逻辑 preMax = Math.max(preMax,height[left]); behMax = Math.max(behMax,height[right]); if(preMax < behMax){ ans += preMax - height[left]; left++; } else{ ans += behMax - height[right]; right--; } } return ans; } }时间复杂度：O(N)
空间复杂度：O(1)
核心：Math.min(preMax,behMax) - height[i]
单调栈：
class Solution { public int trap(int[] height) { int ans = 0; Deque<Integer> stack = new ArrayDeque<>(); for(int i = 0;i<height.length;i++){ while(!stack.isEmpty() && height[stack.peek()]<height[i]){ int bottom = height[stack.pop()]; if(stack.isEmpty()){ break; } int left = stack.peek(); int h = Math.min(height[left],height[i])-bottom; ans += h*(i-left-1); } stack.push(i); } return ans; } }时间复杂度：O(N)
空间复杂度：O(N)