public static int woodEffect(int[][] woods,int m,int n){ int total=0; for(int i=1;i<m-1;i++){ for(int j=1;j<n-1;j++){ int upnum=woods[i-1][j]; int downnum=woods[i+1][j]; int leftnum=woods[i][j-1]; int rightnum=woods[i][j+1]; int num=woods[i][j];
int min=99;
int x=i; int y=j; while(x>0){ x--; if(woods[x][y]>=num){ upnum=woods[x][y]; } } if(min>upnum){ min=upnum; }
那如果二维数组为：
9 9 9 9 9
9 1 5 1 9
9 5 6 5 9
9 2 5 2 9
9 9 9 9 9
按照你的计算方法，上面数字6就积水为0
实际上它的积水应该是3才对吧
找出这个二维数组形成木桶时最短那块板，木桶的桶高是有这个数组的“四边”所构成，即a[0][0]...a[0][N-1],a[0][N-1]...a[M-1][N-1],a[M-1][N-1]...a[M-1][0],a[M-1][0]...a[0][0],把这些都放进一个数组，然后找出最小的那个数，也就是最短的木板。然后把除了四边的那些数与这个最短的木板作差，负数则能储水；正数刚高于最低桶边，不能储水，无视之
× 代表板块无用
+ 代表板块边界
- 代表此板块能盛水
首先图形的四个角为× 板块不可用
剩余的便为+ 暂时作为边界
考虑边界内的板块中贴着边界的板块，
if（此板块的值>=边界的值）
{
边界+ 变为×；此板块作为边界，变为+
}
else
{
此板块标志为- ，表示该板块能盛水
}
最后会暂时形成两个结果
1，一个大桶，此时最简单，取该桶最短板，然后与桶内板块比较， 获得暂时盛水量
2，多个大桶，分别取桶最短板，然后与桶内板块比较，相加， 获得暂时盛水量这时，第二个问题出现了，大桶内或许还有更深的桶，例如6L所举例这个时候对桶进行分析，将桶内盛水板块补充为最短边界，这样边界就失效的，继续按照开始所说，
求边界，得到大桶，然后递归分析，直到桶内再没有桶为止
每次取得的暂时盛水量相加，即可得到最终取水量！
package xj;public class wood {
public static int woodEffect(int[][] woods,int m,int n){
int total=0;
for(int i=1;i<m-1;i++){
for(int j=1;j<n-1;j++){ int upnum=woods[i-1][j];
int downnum=woods[i+1][j];
int leftnum=woods[i][j-1];
int rightnum=woods[i][j+1];
int num=woods[i][j];
int min=99;
int x=i;
int y=j;
while(x>0){
x--;
if(woods[x][y]>=num){
upnum=woods[x][y];
}
} if(min>upnum){
min=upnum;
}
x=i;
y=j;
while(x<m-1){
x++;
if(woods[x][y]>=num){
downnum=woods[x][y];
}
} if(min>downnum){
min=downnum;
}
x=i;
y=j;
while(y>0){
y--;
if(woods[x][y]>=num){
leftnum=woods[x][y];
}
}
if(min>leftnum){
min=leftnum;
}
x=i;
y=j;
while(y<n-1){
y++;
if(woods[x][y]>=num){
rightnum=woods[x][y];
}
}
if(min>rightnum){
min=rightnum;
}
total+=min-num; } }
return total;
}
public static void main(String[] args) {
// int[][] woods={{9,9,9,9},{3,0,0,9},{7,8,9,6}};
int[][] woods={{9,9,9,9,9},{9,1,5,1,9},{9,5,6,5,9},{9,2,5,2,9},{9,9,9,9,9}}; System.out.println(wood.woodEffect(woods,5,5));
}
}
看了半天，后面这段还不是看的很明白啊，解题思路没明确，程序还能实现么？？？
后面这段我举个例子吧
5 2 2 6 6 6 6 6 8 6
5 6 6 5 5 5 5 5 5 6
2 6 5 5 8 8 8 5 5 6
6 5 5 5 8 3 7 5 5 6
5 6 5 5 8 8 7 5 5 6
5 7 5 5 5 5 5 5 5 6
6 6 6 6 6 6 6 6 6 6
经过图形化（无用板块不显示 边界显示为数字）
6 6 6 6 6 8
6 - - - - - - 6
6 - - - - - - - 6
6 - - - - - - - - 6
6 - - - - - - - 6
7 - - - - - - - 6
6 6 6 6 6 6 6
这显示的是一个大桶
用边界中最小值6减去桶内“-”所代表的值 负数舍去 正数留下，得到就是一次暂时盛水量x（先设为x，我就不一一计算了）
然后把所有的“-”值补满为边界最小值6（大于6的不变），得到二维数组
6 6 6 6 6 8
6 6 6 6 6 6 6 6
6 6 6 8 8 8 6 6 6
6 6 6 6 8 6 7 6 6 6
6 6 6 8 8 7 6 6 6
7 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6
继续图形化
8
8 - 7
8
此时在大桶内有一个小桶 边界最小值为7
此时里面的“-”的值已经补满为6
所以二次得到的暂时盛水量为1
然后把所有的“-”值补满为边界最小值7（大于7的不变），得到二维数组
8
8 7 7
8
此时没有再图形化停止查找(如果有，继续，如果没有就结束)
最终的盛水量为 = x + 1对于多个桶的，那就分别查找
方法是递归调用
总结一下啊
1，查找边界
2，获得大桶
3，算出暂时盛水量
4，将里面所有的值补满为大桶边界最小值（大于该边界最小值的就不变）
5，继续1，2，3，4，5，知道没有大桶存在
http://blog.jobbole.com/50705/
原文：http://qandwhat.runkite.com/i-failed-a-twitter-interview/你这个是二维，更难
“墙”的任务就是通知它周围的方格它有多高，方格收到高度h1后进行判断，如果h1小于它自身高顿h2，那么这个方格的身份就由“底”变为“墙”；如果h1大于它自身高顿h2，那么接着和方格前面接收的最低高度h3比较，如果h1<h3，方格就有义务把这个高度h1通知它周围的方格。
package com.cch.waterhole;import java.util.HashMap;
import java.util.Map;public class MainClass {
public static void main(String[] args) {
MainClass caculate=new MainClass(10,10);
caculate.printHeight();
caculate.tellNeighbour(0, 0, 0);
System.out.println("------------------------------");
caculate.printWaterH();
System.out.println("------------------------------");
System.out.println("总共可以装："+caculate.getWater());
}
public MainClass(){
this(10,10);
}
public MainClass(int m,int n){
if(m<3||n<3){
System.out.println("给定值的太小");
m=3;
n=3;
}
this.m=m;
this.n=n;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
Block tempBlock=new Block(i, j);
tempBlock.setHeight((int) (Math.random()*10));
if(i==0||j==0||i==m-1||j==n-1){
tempBlock.setWall(true);
}
data.put(i+","+j, tempBlock);
}
}
}
public void tellNeighbour(int x,int y,int height){
Block tempBlock=data.get(x+","+y);
if(tempBlock==null){
return;
}
if(tempBlock.isWall()||height<tempBlock.getHeight()){
if(tempBlock.getTellState()){
return;
}
tempBlock.setTellState(true);
tempBlock.setWall(true);
height=tempBlock.getHeight();
tellNeighbour(x+1,y,height);
tellNeighbour(x,y-1,height);
tellNeighbour(x-1,y,height);
tellNeighbour(x,y+1,height);
}else {
if(height<tempBlock.getWaterH()){
tempBlock.setWaterH(height);
tellNeighbour(x+1,y,height);
tellNeighbour(x,y-1,height);
tellNeighbour(x-1,y,height);
tellNeighbour(x,y+1,height);
}
}
}
public void printHeight(){
for(int i=0;i<this.m;i++){
for(int j=0;j<this.n;j++){
Block tempBlock=data.get(i+","+j);
System.out.print(tempBlock.getHeight()+" ");
}
System.out.println();
}
}
public void printWaterH(){
for(int i=0;i<this.m;i++){
for(int j=0;j<this.n;j++){
Block tempBlock=data.get(i+","+j);
if(tempBlock.isWall()){
System.out.print(tempBlock.getHeight()+". ");
}else{
System.out.print(tempBlock.getHeight());
System.out.print(tempBlock.getWaterH()+" ");
}
}
System.out.println();
}
}
public int getWater(){
int sum=0;
for(int i=0;i<this.m;i++){
for(int j=0;j<this.n;j++){
Block tempBlock=data.get(i+","+j);
if(!tempBlock.isWall()){
sum+=tempBlock.getWaterH()-tempBlock.getHeight();
}
}
}
return sum;
}
private int m;
private int n;
private Map<String,Block> data=new HashMap<String, Block>();
}class Block{
private int x;
private int y;
private int height;
private int waterH;
private boolean wall;
private boolean tellState;
public Block(int x,int y){
this.x=x;
this.y=y;
waterH=100;
tellState=false;
wall=false;
}
public int getX() {
return x;
} public int getY() {
return y;
} public int getHeight() {
return height;
} public void setHeight(int height) {
this.height = height;
} public int getWaterH() {
return waterH;
} public void setWaterH(int waterH) {
this.waterH = waterH;
} public boolean isWall() {
return wall;
} public void setWall(boolean wall) {
this.wall = wall;
} public boolean getTellState() {
return tellState;
} public void setTellState(boolean tellState) {
this.tellState = tellState;
}
}
程序里随机生成一组数据，最大高度为9。
第一段输出是每个方格的高度，第二段输出是通知之后的结果，每组输出分成两部分，前一个数字表示方块高度，第二个如果是“.”表示这个方块是“墙”，数字表示这个方块的水面高度
1：先找到二维数组里面的最小数（例如是a点）
2：然后找到这个最小数周围上下左右四个数中最小值（例如是b点）
3：判断不点是不是在周边，如果是这就是b-a,
4：如果不是，就把b-a加入一个全局变量，把二维数组中的a点数值改成b点数值
5：一直循环判断，到最后找到结果。
当然这只是一个大致的思路，中间还要判断a,b如果相等怎么处理，还要就是如果a点的周围的四个数都相等，也要跳出循环。这个只是我的一个大致思路，第一次写这个，有些写的不明白，也许也是错的思路。
首先，将可以积水的位置看做A（包括积水量为0），那么，A满足以下两个条件：
1、A所在行前后必定存在≥A的数字
2、A所在列上下必定存在≥A的数字
计算A的积水量：
1、A所在行的位置前面的数字的最大值与A所在行的位置后面的数字的最大值，取其小者（假设为R）。
2、A所在列的位置上面的数字的最大值与A所在列的位置下面的数字的最大值，取其小者（假设为C）。
3、A的积水量=min(R-A,C-A)
4、sum(A)即为该二维数组的所有积水量
个人感觉就是一个最大值利用的问题。不知道说的是否正确？
static int N = 0; // 列：有效范围[0,N)
final static int GRID_HEIGHT = 0; // 方格属性下标0：方格高度
final static int GRID_WATER = 1; // 方格属性下标1：储存水量
static int[][][] gridArray; // 方格二维数组：M行 * N列 * 方格属性
static int maxHeight = 0; // 方格高度最大值 final static int INVALID_VALUE = -1; // 无效值 public static void main(String[] args) {
preprocess(); // 预处理
addWater(); // 加满水
while (removeWater()) { } // 移除水（直到无法再移除任何方格的水时停止）
postprocess(); // 后处理
} private static void preprocess() { // 预处理
System.out.println("请输入方格二维数组的行数：");
do {
try {
M = (new Scanner(System.in)).nextInt();
} catch(Exception e) {
M = INVALID_VALUE;
}
} while(M == INVALID_VALUE); System.out.println("请输入方格二维数组的列数：");
do {
try {
N = (new Scanner(System.in)).nextInt();
} catch(Exception e) {
N = INVALID_VALUE;
}
} while(N == INVALID_VALUE); // 方格二维数组初始化
System.out.println("请输入方格二维数组的数值：");
gridArray = new int[M][N][GRID_WATER + 1];
for (int m = 0; m < M; m++) {
for (int n = 0; n < N; n++) {
do {
try {
gridArray[m][n][GRID_HEIGHT] = (new Scanner(System.in)).nextInt();
} catch(Exception e) {
gridArray[m][n][GRID_HEIGHT] = INVALID_VALUE;
}
} while(gridArray[m][n][GRID_HEIGHT] == INVALID_VALUE);
gridArray[m][n][GRID_WATER] = 0;
}
} printArray(GRID_HEIGHT);
} private static void addWater() { // 加满水
// 方格高度最大值设定
for (int m = 0; m < M; m++) {
for (int n = 0; n < N; n++) {
if (maxHeight < gridArray[m][n][GRID_HEIGHT]) {
maxHeight = gridArray[m][n][GRID_HEIGHT];
}
}
} // 加满水
for (int m = 0; m < M; m++) {
for (int n = 0; n < N; n++) {
gridArray[m][n][GRID_WATER] = maxHeight - gridArray[m][n][GRID_HEIGHT];
}
}
System.out.print("加满水后，");
printArray(GRID_WATER);
} private static boolean removeWater() { // 移除水
for (int m = 0; m < M; m++) {
for (int n = 0; n < N; n++) {
if (canRemoveWater(m, n)) { // 还能移除水
System.out.print("移除水后，");
printArray(GRID_WATER);
return true; // 继续尝试移除水
}
}
}
return false; // 直到无法再移除任何方格的水时停止
} private static boolean canRemoveWater(final int m, final int n) { // 能否移除水
boolean returnValue = false; if (gridArray[m][n][GRID_WATER] > 0) { // 有水才有可能移除
if (m == 0 || m == M -1 || n == 0 || n == N -1) { // 边界上的水都可以移除
gridArray[m][n][GRID_WATER] = 0;
returnValue = true;
} else { // 非边界上的,如果高于周围的水都可以移除
if (gridArray[m ][n ][GRID_WATER] + gridArray[m ][n ][GRID_HEIGHT] >
gridArray[m-1][n ][GRID_WATER] + gridArray[m-1][n ][GRID_HEIGHT]) { // 上
gridArray[m ][n ][GRID_WATER] =
gridArray[m-1][n ][GRID_WATER] + gridArray[m-1][n ][GRID_HEIGHT]
- gridArray[m ][n ][GRID_HEIGHT];
if (gridArray[m ][n ][GRID_WATER] < 0) {
gridArray[m ][n ][GRID_WATER] = 0;
}
returnValue = true;
}
if (gridArray[m ][n ][GRID_WATER] + gridArray[m ][n ][GRID_HEIGHT] >
gridArray[m+1][n ][GRID_WATER] + gridArray[m+1][n ][GRID_HEIGHT]) { // 下
gridArray[m ][n ][GRID_WATER] =
gridArray[m+1][n ][GRID_WATER] + gridArray[m+1][n ][GRID_HEIGHT]
- gridArray[m ][n ][GRID_HEIGHT];
if (gridArray[m ][n ][GRID_WATER] < 0) {
gridArray[m ][n ][GRID_WATER] = 0;
}
returnValue = true;
}
if (gridArray[m ][n ][GRID_WATER] + gridArray[m ][n ][GRID_HEIGHT] >
gridArray[m ][n-1][GRID_WATER] + gridArray[m ][n-1][GRID_HEIGHT]) { // 左
gridArray[m ][n ][GRID_WATER] =
gridArray[m ][n-1][GRID_WATER] + gridArray[m ][n-1][GRID_HEIGHT]
- gridArray[m ][n ][GRID_HEIGHT];
if (gridArray[m ][n ][GRID_WATER] < 0) {
gridArray[m ][n ][GRID_WATER] = 0;
}
returnValue = true;
}
if (gridArray[m ][n ][GRID_WATER] + gridArray[m ][n ][GRID_HEIGHT] >
gridArray[m ][n+1][GRID_WATER] + gridArray[m ][n+1][GRID_HEIGHT]) { // 右
gridArray[m ][n ][GRID_WATER] =
gridArray[m ][n+1][GRID_WATER] + gridArray[m ][n+1][GRID_HEIGHT]
- gridArray[m ][n ][GRID_HEIGHT];
if (gridArray[m ][n ][GRID_WATER] < 0) {
gridArray[m ][n ][GRID_WATER] = 0;
}
returnValue = true;
}
}
} return returnValue;
} private static void postprocess() { // 后处理
int totalWater = 0; // 合计储存水量
for (int m = 0; m < M; m++) {
for (int n = 0; n < N; n++) {
totalWater += gridArray[m][n][GRID_WATER];
}
}
System.out.println("合计储存水量" + "：" + totalWater);
} private static void printArray(final int gridIndex) { // 打印数组
switch (gridIndex) {
case GRID_HEIGHT:
System.out.println("方格高度" + "：");
break;
case GRID_WATER:
System.out.println("储存水量" + "：");
break;
default:
break;
}
for (int m = 0; m < M; m++) {
for (int n = 0; n < N; n++) {
System.out.print(gridArray[m][n][gridIndex] + " ");
}
System.out.println();
}
}
}
1.我想说的是，你的if...else...块考虑应该有纰漏，或许我没理解你的意思，但是是一个大桶/多个大桶没阐述清楚，不过同样谢谢你对本帖的关注。
2.通过10次的针对性及2000多次的随机测试，你们的答案全部吻合，这说明你们的思路和程序都是正确的，计算出来的值也是正确的，程序和思路我会仔细看的。
3.你的思路貌似不清晰，考虑有点不周全
4.你们的思路基本是相近的，不过这样是不可行的，因为判断该数所在行及列是不够的，因为水不一定只从该行或列流走，从任意一个低于它的相邻的格子都可以流走。
例如： 按照24L的步骤，4处的积水应该是min(9, 9)=9了，应该是0吧。
9 9 9 9 9
9 4 9 9 9
9 4 2 9 9
9 9 1 1 9
9 9 9 0 9
http://blog.jobbole.com/50705/
感觉和这里两篇分析twitter面试问题很接近。
0 0 0 0 0 0
0 9 9 9 9 0
0 3 0 0 9 0
0 7 8 9 6 0
0 0 0 0 0 0
设s=0。从[1,1]坐标开始到[m-1,n-1]坐标结束，进行遍历。设被遍历的坐标上的数字是k，在设它的八个方位中的最小数字是min，比较它与min的大小。如果k>=min，不做处理；如果k<min，s+=min-k。