【宫水三叶の真题精选】一题四解:朴素解法 & 预处理最值 & 单调栈 & 面积差

您所在的位置:网站首页 宫水三叶长大后图片 【宫水三叶の真题精选】一题四解:朴素解法 & 预处理最值 & 单调栈 & 面积差

【宫水三叶の真题精选】一题四解:朴素解法 & 预处理最值 & 单调栈 & 面积差

2024-07-11 20:22| 来源: 网络整理| 查看: 265

朴素解法

对于每根柱子而言,我们只需要找出「其左边最高的柱子」和「其右边最高的柱子」。

对左右的最高柱子取一个最小值,再和当前柱子的高度做一个比较,即可得出当前位置可以接下的雨水。

同时,边缘的柱子不可能接到雨水(某一侧没有柱子)。

这样的做法属于「暴力做法」,但题目没有给数据范围,我们无法分析到底能否 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