动态规划,积水体量

标题链接: https://leetcode.com/problems/trapping-rain-water/?tab=Description

  不说废话了,直接贴题

图片 1

题意

给你一个二维矩阵,权值为False和True,找到一个最大的矩形,使得里面的
值全部为True,输出它的面积

 

样例

给你一个矩阵如下

[
  [1, 1, 0, 0, 1],
  [0, 1, 0, 0, 1],
  [0, 0, 1, 1, 1],
  [0, 0, 1, 1, 1],
  [0, 0, 0, 0, 1]
]
输出6

Problem: 依照所给数组的值,依照上海教室的示意图。求解积水最大体量。

1.两手空空模型

  这几个题假设直接来化解的话,大概有十分大的难度,所以,大家必须先成立模型。
  首先大家来看3个题,是LeetCode上:

 

题意

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find 
the area of largest rectangle in the histogram.

图片 2

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

图片 3

 

样例

For example,
Given heights = [2,1,5,6,2,3],
return 10.

第1对所给数组进行遍历操作,求出最大惊人所对应的下标为maxIndex

(1).暴力解法

  这一个题暴力解法相当的简约,便是遍历数组,向前和向后总结当前柱状图能够整合的最大矩形。至于解法那里不详述,我们的目标引出另四个主意。

 

(2).栈法

  解题思路:首先大家将首先个柱状图在数组里面包车型大巴下标(之后称为下标)压栈,之后的柱状图须求大家来判定是或不是须求压栈。假设新的柱状图中度当先栈顶柱状图的高度,那么就现阶段以此柱状图的下标压栈;倘使低于的话,那么大家能够总括当前栈顶及其在此之前的柱状图面积,于是,大家将栈顶的下标pop出来,计算它的面积。
  pop之后,大家重新判断当前的栈顶的可观是不是超出新柱状图的冲天,倘若超出,则压栈;反之,则总计面积,那里总计面积的时候必要专注的是:总计pop出来的柱状图的面积(从pop出来的柱状图到新的柱状图,不带有新的柱状图,因为新的柱状图的惊人小于当前pop出来的可观)中度等于它自身的可观,而宽度则是日前的新的柱状图的下标-pop出来的事后的栈顶的下标

  • 1。
      为何是如此吧?因为pop出来的之后的栈顶柱状图与pop出来的柱状图之间大概还有别的柱状图,只是在事先的操作被pop出去了,所以,这里要求这么测算宽度。
      如若知道了思路,那么代码就可怜清楚了

    public int largestRectangleArea(int[] heights) {

          if (heights == null || heights.length == 0) {
              return 0;
          }
          Stack<Integer> stack = new Stack<>();
          //压入第一个柱状图的下标
          stack.push(0);
          int i = 1;
          int max = heights[0];
          //当i < heights.length 或者栈不为空时,这里之所以需要判断栈不为空,是因为
          //可能有些高度很小的柱状图,一直停留在栈中,没有机会pop出来计算面积,所以最后需要一一的pop出来
          //计算面积
          while (i < heights.length || (i == heights.length && !stack.isEmpty())) {
              //当当前的高度大于大于栈顶的高度或者栈为空时,将当前的下标压栈
              if (i < heights.length && (stack.isEmpty() || heights[stack.peek()] <= heights[i])) {
                  stack.push(i);
                  i++;
              } else { //计算面积
                  int top = heights[stack.pop()]; //得到栈顶的高度
                  //计算面积,当当前的栈为空时,直接是top * i(i里面已经包含了中间被pop出去的柱状图);不为空时,
                  //则使用相对位置计算
                  int currMax = !stack.isEmpty() ? (i - stack.peek() - 1) * top : top * i;
                  //更新最大值
                  max = Math.max(max, currMax);
              }
          }
          return max;
      }
    

之后从左向右进行遍历,设置左侧中度为left马克斯 并开始化为
height[0],从i==1到i==maxIndex实行遍历。不断更新water,以及leftMax

2.施用模型消除难点

  未来赶回大家要化解的难点上去,我们选用类似于地点的法子来消除,将数组转换:

0 0 1 1 0 -> 0 0 1 1 0
0 0 1 1 0 -> 0 0 2 2 0
1 1 0 0 0 -> 1 1 0 0 0
1 1 1 0 0 -> 2 2 1 0 0

  需求留意的是,转换的规则是:每行的遍历,要是当前岗位(假如nums[i][j])为true,那么dp[i]j
= dp[i – 1][j – 1];反之,假诺为false,则置为0。当i =
0时,另当别论。
  数组转换来功现在,大家只要求总结每一行的最大矩形面积,当中dp数组中0,1,2等等的意味的这一个矩形的惊人,当每一行的最大矩形都计算出来之后,取得最大值自然是最后的答案

public int maximalRectangle(boolean[][] matrix) {
        if (matrix == null || matrix[0].length == 0) {
            return 0;
        }
        //转换之后的数组
        int dp[][] = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (i == 0) {
                    //i = 0的情况
                    dp[i][j] = matrix[i][j] ? 1 : 0;
                } else {
                    //不等于0
                    dp[i][j] = matrix[i][j] ? dp[i - 1][j] + 1 : 0;
                }
            }
        }
        int max = 0;
        //遍历每一行
        for (int i = 0; i < matrix.length; i++) {
            //取得每一行的最大值
            int temp = findRowMax(dp[i]);
            //更新最大值
            max = Math.max(max, temp);
        }
        return max;
    }

    private int findRowMax(int[] heights) {
        if (heights.length == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(heights[0]);
        int i = 1;
        int max = heights[0];
        while (i < heights.length || (i == heights.length && !stack.isEmpty())) {
            if (i < heights.length && (stack.isEmpty() || heights[i] >= heights[stack.peek()])) {
                stack.push(i);
                i++;
            } else {
                int height = heights[stack.pop()];
                int currMax = !stack.isEmpty() ? (i - stack.peek() - 1) * height : height * i;
                max = Math.max(currMax, max);
            }
        }
        return max;
    }

    当height[I]小于leftMax时,water += leftMax – height

    当height[i]大于leftMax时,leftMax = height[I]

 

之后从i==height.length – 2到下标 I == maxIndex举办遍历操作
初步化rightMax = height[height.length-1]

   
当height[I]小于rightMax时,water+=rightMax – height[I]

   
当height[I]大于rightMax时,rightMax = height[I]

 

函数结果重回water

 

参考代码:

 

package leetcode_50;


/***
 * 
 * @author pengfei_zheng
 * 求积水的体积
 */
public class Solution42 {
    public static int trap(int[] height) {
        if (height.length <= 2) return 0;
        int max = -1;
        int maxIndex = 0;
        for (int i = 0; i < height.length; i++) {
            if (height[i] > max) {
                max = height[i];
                maxIndex = i;
            }
        }

        int leftMax = height[0];
        int water = 0;
        for (int i = 1; i < maxIndex; i++) {
            if (height[i] > leftMax) {
                leftMax = height[i];
            } else {
                water += leftMax - height[i];
            }
        }

        int rightMax = height[height.length - 1];
        for (int i= height.length - 2; i > maxIndex; i--) {
            if (height[i] > rightMax) {
                rightMax = height[i];
            } else {
                water += rightMax - height[i];
            }
        }

        return water;
    }
    public static void main(String[]args){
//        int []height={0,1,0,2,1,0,1,3,2,1,2,1};
        int []height={10,0,11,0,10};
        System.out.println(trap(height));
    }
}

 

相关文章