M*****e
发帖数: 568 | 1 之前帖子的一道题，没有想到特elegant的解法。主要是需要一个list存储能够蓄水的
点，而这些点选择的标准是不能小于当前点和list中的前一个点，说起来比较绕口。
不要说从左扫一个从右扫一个的解法，这种解法没办法解决中间有两个峰的情况，比如
3 1 8 1 9 1 5 => 2+7+4=13
X）Onsite 老题新酒，直方图，天上下雨，求能存多少水
E.G:
3,1,5 => 2
3,1,0,5 => 5
很假单的O(N)扫描就行
扩展是改成Online的算法，就是说：
有些地方高度随时会变，
E.G.
3,1,5 => 3,0,5 => 3
3,1,0,5 => 3,3,0,5 => 3
设计一个算法，最快的返回改变高度之后的结果 | p*****2
发帖数: 21240 | | p*****2
发帖数: 21240 | 3 public class test2
{
static int water(int[] arr)
{
int i = 0;
int j = arr.length - 1;
int count = 0;
while (i < j)
{
while (i < j && arr[i] < arr[i + 1])
i++;
while (j > i && arr[j] < arr[j - 1])
j--;
if (i == j)
break;
int start;
int low;
boolean direct = true;
if (arr[i] <= arr[j])
{
start = i + 1;
low = arr[i];
direct = true;
}
else
{
start = j - 1;
low = arr[j];
direct = false;
}
while (arr[start] < low)
{
count += low - arr[start];
if (direct)
start++;
else
start--;
}
if (direct)
i = start;
else
j = start;
}
return count;
}
public static void main(String[] args)
{
int[][] q = new int[][]
{
{ 3, 1, 5 },
{ 3, 1, 0, 5 },
{ 1, 2, 3 },
{ 3, 2, 1 },
{ 1, 2, 3, 2, 1 },
{ 5, 4, 3, 6, 2, 3 },
{ 3, 1, 8, 1, 9, 1, 5 } };
int[] a = new int[]
{ 2, 5, 0, 0, 0, 4, 13 };
for (int i = 0; i < q.length; i++)
{
int r = water(q[i]);
if (a[i] == r)
System.out.print("[Pass]");
else
System.out.print("[Fail]");
System.out.println("expected:" + a[i] + " actual:" + r);
}
}
} | w****x
发帖数: 2483 | 4 int CalculateContain(int a[], int n)
{
assert(a && n > 0);
int nRet = 0;
stack stk;
for (int i = 0; i < n; i++)
{
if (!stk.empty() && a[stk.top()] < a[i])
{
int nPrev = stk.top();
stk.pop();
while (!stk.empty() && a[stk.top()] <= a[i])
{
int nCur = stk.top();
stk.pop();
int nLimit = a[nCur] <= a[i] ? a[nCur] : a[i];
nRet += (nLimit - a[nPrev]) * (i - 1 - nCur);
nPrev = nCur;
}
// missing this logic!!
if (!stk.empty())
nRet += (a[i] - a[nPrev]) * (i - 1 - stk.top());
}
stk.push(i);
}
return nRet;
} | M*****e
发帖数: 568 | 5 没有看到你后面用start附回ij的那一段。
不过我想的是一边从左向右的扫描就把所有的interval找出来。
就是退栈的操作比较不好证明。
你这种左扫右扫可能还更容易说明一些。
【在 p*****2 的大作中提到】
: public class test2
: {
: static int water(int[] arr)
: {
: int i = 0;
: int j = arr.length - 1;
: int count = 0;
: while (i < j)
: {
: while (i < j && arr[i] < arr[i + 1])
| i**********e
发帖数: 1145 | 6 火鸡那解法是最好的，O(n) 时间 O(1) 空间 又不容易出错：
http://www.mitbbs.com/article_t/JobHunting/31983619.html
我照着火鸡思路写的 C++:
int trap(int A[], int n) {
int h = 0;
for (int i = 1; i < n; i++) {
if (A[i] > A[h]) {
h = i;
}
}
int left = 0;
int total = 0;
for (int i = 0; i < h; i++) {
if (A[i] > A[left]) {
left = i;
} else {
total += A[left] - A[i];
}
}
int right = n-1;
for (int i = n-1; i > h; i--) {
if (A[i] > A[right]) {
right = i;
} else {
total += A[right] - A[i];
}
}
return total;
}
stack 的解法是 O(n) 时间 O(n) 空间，而且不容易写对。边界条件很多，要考虑很多情况，这里是一个我实现的：
int trap(int A[], int n) {
stack s;
int total = 0;
int h = 0;
for (int R = 0; R < n; R++) {
while (!s.empty()) {
int L = s.top();
total += (R-L-1) * (min(A[L], A[R]) - h);
h = A[L];
if (A[L] > A[R]) break;
s.pop();
}
s.push(R);
}
return total;
} | M*****e
发帖数: 568 | 7
写了一个扫一遍找出每个interval关键点，然后算水量的
int WaterInArray(vector data)
{
vector keys(data.size());
int open = -1;
for (int i=0; i
{
while (open>0 && data[i]>data[keys[open]] && data[keys[open]]
keys[open-1]])
open--;
keys[++open] = i;
}
int total = 0, pos = 0;
while (pos < open)
{
int min = (data[keys[pos]]
data[keys[pos+1]];
for (int i=keys[pos]+1; i
{
if (min > data[i])
total += min - data[i];
}
pos++;
}
return total;
}
【在 M*****e 的大作中提到】
: 没有看到你后面用start附回ij的那一段。
: 不过我想的是一边从左向右的扫描就把所有的interval找出来。
: 就是退栈的操作比较不好证明。
: 你这种左扫右扫可能还更容易说明一些。
| h**********l
发帖数: 6342 | 8 后两个for 应该从1 和n-2开始，估计你写顺手了
【在 i**********e 的大作中提到】
: 火鸡那解法是最好的，O(n) 时间 O(1) 空间 又不容易出错：
: http://www.mitbbs.com/article_t/JobHunting/31983619.html
: 我照着火鸡思路写的 C++:
: int trap(int A[], int n) {
: int h = 0;
: for (int i = 1; i < n; i++) {
: if (A[i] > A[h]) {
: h = i;
: }
: }
| l*********8
发帖数: 4642 | 9 Yes, logically the for loops should start from 1 and n-2.
But ihasleetcode's code can get the same results.
【在 h**********l 的大作中提到】
: 后两个for 应该从1 和n-2开始，估计你写顺手了
| h**********l
发帖数: 6342 | 10 不会把，如果最边上的短的话，假设是0， 显然就多 计算了阿
【在 l*********8 的大作中提到】
: Yes, logically the for loops should start from 1 and n-2.
: But ihasleetcode's code can get the same results.
| | | l*********8
发帖数: 4642 | 11 int left = 0;
int total = 0;
for (int i = 0; i < h; i++) {
if (A[i] > A[left]) {
left = i;
} else {
total += A[left] - A[i];
}
}
In the loop, when i is 0,
total += A[left] - A[i]
is executed.
which is total += A[0] - A[0]. It has no influence to the result.
【在 h**********l 的大作中提到】
: 不会把，如果最边上的短的话，假设是0， 显然就多 计算了阿
| C***U
发帖数: 2406 | 12 你这明显误导别人啊
左扫一遍右扫一遍 就可以
【在 M*****e 的大作中提到】
: 之前帖子的一道题，没有想到特elegant的解法。主要是需要一个list存储能够蓄水的
: 点，而这些点选择的标准是不能小于当前点和list中的前一个点，说起来比较绕口。
: 不要说从左扫一个从右扫一个的解法，这种解法没办法解决中间有两个峰的情况，比如
: 3 1 8 1 9 1 5 => 2+7+4=13
: X）Onsite 老题新酒，直方图，天上下雨，求能存多少水
: E.G:
: 3,1,5 => 2
: 3,1,0,5 => 5
: 很假单的O(N)扫描就行
: 扩展是改成Online的算法，就是说：
| d****n
发帖数: 233 | 13 You can scan from left to right and from right to left.
int trap(int A[], int n) {
int total = 0;
int temp = 0;
int h = 0;
for (int i = 0; i < n; i++) {
if (A[i] < h) {
temp += h - A[i];
} else {
total += temp;
h = A[i];
temp = 0;
}
}
h = 0;
temp = 0;
for (int i = n-1; i >=0; i--) {
if (A[i] <= h) {
temp += h - A[i];
} else {
total += temp;
h = A[i];
temp = 0;
}
}
return total;
}
【在 C***U 的大作中提到】
: 你这明显误导别人啊
: 左扫一遍右扫一遍 就可以
| j*****o
发帖数: 394 | 14 没理解后面这个ONLINE是怎么解的。。
？
【在 M*****e 的大作中提到】
: 之前帖子的一道题，没有想到特elegant的解法。主要是需要一个list存储能够蓄水的
: 点，而这些点选择的标准是不能小于当前点和list中的前一个点，说起来比较绕口。
: 不要说从左扫一个从右扫一个的解法，这种解法没办法解决中间有两个峰的情况，比如
: 3 1 8 1 9 1 5 => 2+7+4=13
: X）Onsite 老题新酒，直方图，天上下雨，求能存多少水
: E.G:
: 3,1,5 => 2
: 3,1,0,5 => 5
: 很假单的O(N)扫描就行
: 扩展是改成Online的算法，就是说：
| C***U
发帖数: 2406 | 15 对啊
我开始也觉得是这样
然后看了这个人说得 我以为那样是不对
后来有人告诉我可以左右各走一边就可以
所以我说楼主的帖子坑爹
自己没搞懂。。。还误导别人
【在 d****n 的大作中提到】
: You can scan from left to right and from right to left.
: int trap(int A[], int n) {
:
: int total = 0;
: int temp = 0;
: int h = 0;
: for (int i = 0; i < n; i++) {
: if (A[i] < h) {
: temp += h - A[i];
: } else {
| m******d
发帖数: 25 | 16 我贡献一个只扫描一遍的算法把。首先用最左和最右计算一个最大可能的雨量。如果左
边比右边低，那么从左边前进一个。如果左边第二个比第一个要低，那么从总水量里减
去左边第二个的高度；否则，用左边第二个和最右边的计算一个新的最大可能的水量。
右边同理。
public class Solution {
public int trap(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
if (A.length < 3){
return 0;
}
int l=0;
int r=A.length-1;
int left=A[l], right=A[r];
int sum = (A[l] < A[r] ? A[l] : A[r]) * (A.length - 2);
while(l
if (left < right){
l++;
if (left < A[l]){
sum -= left;
sum += ((A[l] < right ? A[l] : right) - left) * (r-l-1);
left = A[l];
} else {
sum -= A[l];
}
} else {
r--;
if (right < A[r]){
sum -= right;
sum += ((A[r] < left ? A[r] : left) - right) * (r-l-1);
right = A[r];
} else {
sum -= A[r];
}
}
}
return sum;
}
} | z*****e
发帖数: 231 | 17 贴一个O（n）的，
#include
using namespace std;
int trap(int A[], int n) {
int max=A[0];
int int_max=0;
int area=A[0];
if(n<3) return 0;
for(int i=1;i
{
area+=A[i];
if(A[i]>max)
{
max=A[i];
int_max=i;
}
}
int i=0;
int current=A[i];
int total=current;
i++;
while(i<=int_max)
{
while(current>=A[i])
{
i++;
total+=current;
}
current=A[i];
total+=current;
i++;
}
if(int_max==(n-1))
return total-area;
i=n-1;
current=A[i];
i--;
total+=current;
while(i>int_max)
{
while(current>=A[i])
{
i--;
total+=current;
if(i==int_max) break;
}
if(i==int_max) break;
current=A[i];
total+=current;
i--;
}
return total-area;
}
int main()
{
int A[] = {2, 0, 2};
int result=trap(A,3);
cout<
return 0;
} |
|
