做自己的网站挣钱,网站seo合同,美食网站网页设计代码,三维家设计新手教学教程题目#xff1a;
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。
方法一#xff08;相向双指针#xff09;#xff1a;竖着计算面积
代码#xff1a;
class Solution {public int trap(int[] he…题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。
方法一相向双指针竖着计算面积
代码
class Solution {public int trap(int[] height) {int ans 0, left 0, right height.length - 1, preMax 0, sufMax 0;while (left right) {preMax Math.max(preMax, height[left]);sufMax Math.max(sufMax, height[right]);ans preMax sufMax ? preMax - height[left] : sufMax - height[right--];}return ans;}
} 方法二单调栈横着计算面积
代码
class Solution {public int trap(int[] height) {int ans 0;DequeInteger st new ArrayDeque();for (int i 0; i height.length; i) {while (!st.isEmpty() height[i] height[st.peek()]) {int bottomH height[st.pop()];if (st.isEmpty()) {break;}int left st.peek();int dh Math.min(height[left], height[i]) - bottomH; // 面积的高ans dh * (i - left - 1);}st.push(i);}return ans;}
}
