给定n个柱面的高度，表示降雨某地n块区域的海拔高度。
计算降雨之后该地最大储水面积。如果低于地平线，也就是小于0，则一定积水。
单调栈 leetcode 42题 接雨水 自己没用编辑器手写了一下 不确定对不对！！！！
//单调栈
public int maxArea(int[] heights){
Stack<Integer> stack = new Stack<>();
int result = 0;
for(int i = 0 ;i < heights.length ; i ++){
while(!stack.isEmpty() && heights[stack.peek()] <= heigths(i)){
int curIndex = stack.pop();
if(stack.isEmpty()) break;
int rigthIndex = i;
int leftIndex = stack.peek();
int d = righhtIndex - leftIndex -1;
int h = Math.min(heights[rightIndex],heights[leftIndex]) - heights[curIndex];
result += d*h;
}
stack.push(i);
}
return result;
}
发表于 2019-08-11 23:25:55
回复(1)
/**
* [1,3,5,2,6,0,9,10,8,2,7]
*
* @param ary
* @return
*/
public static int caclPonding(int[] ary) {
int maxIndex = findMaxIndex(ary);
// 左右分开计算
int sumLeft = caclLeftPonding(ary, 0, maxIndex);
int sumRight = caclRightPonding(ary, maxIndex, ary.length - 1);
return sumLeft + sumRight;
}
private static int caclLeftPonding(int[] ary, int startIndex, int endIndex) {
if (startIndex == endIndex) {// 递归终止
return 0;
}
int leftMaxIndex = findLeftMaxIndex(ary, startIndex, endIndex);
int ponding = caclPonding(ary, leftMaxIndex, endIndex);
return ponding + caclLeftPonding(ary, startIndex, leftMaxIndex);
}
private static int caclRightPonding(int[] ary, int startIndex, int endIndex) {
if (startIndex == endIndex) {// 递归终止
return 0;
}
int rightMaxIndex = findRightMaxIndex(ary, startIndex, endIndex);
int ponding = caclPonding(ary, startIndex, rightMaxIndex);
return ponding + caclRightPonding(ary, rightMaxIndex, endIndex);
}
private static int caclPonding(int[] ary, int startIndex, int endIndex) {
if (endIndex - startIndex < 2) {
return 0;
}
int width = endIndex - startIndex - 1;// 间隔数
int height = ary[startIndex] > ary[endIndex] ? ary[endIndex] : ary[startIndex];// 取小值
int sum = 0;
// 内部实体面积
for (int i = (startIndex + 1); i < endIndex; i++) {
sum += ary[i];
}
return width * height - sum;
}
public static int findMaxIndex(int[] ary) {
int maxIndex = 0;
int max = ary[maxIndex];
int length = ary.length;
for (int i = 1; i < length; i++) {
if (ary[i] > max) {
max = ary[i];
maxIndex = i;
}
}
return maxIndex;
}
public static int findLeftMaxIndex(int[] ary, int startIndex, int endIndex) {
int maxIndex = startIndex;
int max = ary[maxIndex];
for (int i = startIndex; i < endIndex; i++) {
if (ary[i] >= max) {// 相等取最新的下标
max = ary[i];
maxIndex = i;
}
}
return maxIndex;
}
public static int findRightMaxIndex(int[] ary, int startIndex, int endIndex) {
int maxIndex = endIndex;
int max = ary[maxIndex];
for (int i = endIndex; i > startIndex; i--) {
if (ary[i] >= max) {
max = ary[i];
maxIndex = i;
}
}
return maxIndex;
}
发表于 2020-02-13 20:14:33
回复(0)
public int solution(int[] arr){
int sum =0;
Stack<Integer> stack =new Stack<>();//栈里压的是坐标，用来计算长度
for(int i =0;i<arr.length;i++){
if(stack.size()==0) stack.push(i);
else{
if(arr[i]<arr[stack.peek()]) stack.push(i);
else{
int low =arr[stack.poll()];
sum+=(i-stack.peek())*(Math.min(arr[i],arr[stack.poll()])-low);
}
}
return sum;
}
发表于 2019-09-03 09:33:48
回复(0)
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] height = new int[n];
for(int i=0;i<n;i++) {
height[i] = sc.nextInt();
}
int lowest = Integer.MIN_VALUE;
for(int i=0;i<n;i++) {
lowest = Math.min(lowest, height[i]);
}
for(int i=0;i<n;i++) {
height[i] += lowest;
}
LinkedList<Integer> stack = new LinkedList<>();
int maxArea = 0;
int sum =0;
for(int i=0;i<height.length;i++) {
while(!stack.isEmpty()&&height[stack.peekFirst()]<height[i]) {
int temp = stack.pollFirst();
if(stack.isEmpty())
break;
if(height[stack.peek()]==height[temp])
continue;
else {
int h = Math.min(height[i], height[stack.peek()]) - height[temp];
int distance = i - stack.peek() -1;
sum += h*distance;
}
}
if(stack.isEmpty()||i==height.length-1) {
maxArea = Math.max(maxArea, sum);
sum = 0;
}
stack.offerFirst(i);
}
System.out.println(maxArea);
}
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] height = new int[n];
for(int i=0;i<n;i++) {
height[i] = sc.nextInt();
}
int lowest = Integer.MIN_VALUE;
for(int i=0;i<n;i++) {
lowest = Math.min(lowest, height[i]);
}
for(int i=0;i<n;i++) {
height[i] += lowest;
}
LinkedList<Integer> stack = new LinkedList<>();
int maxArea = 0;
int sum =0;
for(int i=0;i<height.length;i++) {
while(!stack.isEmpty()&&height[stack.peekFirst()]<height[i]) {
int temp = stack.pollFirst();
if(stack.isEmpty())
break;
if(height[stack.peek()]==height[temp])
continue;
else {
int h = Math.min(height[i], height[stack.peek()]) - height[temp];
int distance = i - stack.peek() -1;
sum += h*distance;
}
}
if(stack.isEmpty()||i==height.length-1) {
maxArea = Math.max(maxArea, sum);
sum = 0;
}
stack.offerFirst(i);
}
System.out.println(maxArea);
}
}
编辑于 2019-08-28 13:18:18
回复(0)
问题信息
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
