【宫水三叶の真题精选】一题四解:朴素解法 & 预处理最值 & 单调栈 & 面积差 |
您所在的位置:网站首页 › 宫水三叶长大后图片 › 【宫水三叶の真题精选】一题四解:朴素解法 & 预处理最值 & 单调栈 & 面积差 |
朴素解法 对于每根柱子而言,我们只需要找出「其左边最高的柱子」和「其右边最高的柱子」。 对左右的最高柱子取一个最小值,再和当前柱子的高度做一个比较,即可得出当前位置可以接下的雨水。 同时,边缘的柱子不可能接到雨水(某一侧没有柱子)。 这样的做法属于「暴力做法」,但题目没有给数据范围,我们无法分析到底能否 AC。 唯唯诺诺交一个,过了 ~ (好题,建议加入蓝桥杯 代码: class Solution { public long maxWater(int[] height) { int n = height.length; long ans = 0; for (int i = 1; i < n - 1; i++) { int cur = height[i]; // 获取当前位置的左边最大值 int l = Integer.MIN_VALUE; for (int j = i - 1; j >= 0; j--) l = Math.max(l, height[j]); if (l |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |