Archive for October 3rd, 2013
DP是O(n2)的解法。新开一个数列B，B[i]表示以A[i]结尾的LIS的最大长度。每次在i处往前看，若j<i，则以i结尾的就只少>=B[j] + 1。
public int getLIS(int[] A) {
int[] B = new int[A.length];
int max = 1;
B[0] = 1;
for (int i = 1; i < A.length; i++) {
B[i] = 1;
for (int j = i - 1; j >= 0; j--) {
if (A[i] > A[j]) {
B[i] = Math.max(B[i], B[j] + 1);
max = Math.max(B[i], max);
}
}
}
return max;
}
- In: leetcode
- 2 Comments
这题不好想，还是看了答案才明白。中心思路是：每个bar头顶能接多少水，取决于它两边有木有比自己高的两个木板，有的话自己上方就被trap住了，trap的volumn是（两边比自己高的那两个模板中的短板-自己的高度）×1。
然后就要考虑怎么求在每个木板i，他的左边最高板和右边最高板的值呢？用dp一试就出来了。这个就是因为很熟练LIS了，所以一下就做出来了。这种接水题也是，现在觉得难，多做几道思路就清晰了吧。
public int trap(int[] A) {
int[] left = new int[A.length];
int[] right = new int[A.length];
for (int i = 0; i < A.length; i++) {
left[i] = i > 0 ? Math.max(left[i - 1], A[i]) : A[i];
}
for (int i = A.length - 1; i >= 0; i--) {
right[i] = i < A.length - 1 ? Math.max(right[i + 1], A[i]) : A[i];
}
int res = 0;
for (int i = 1; i < A.length - 1; i++) { //two edges can't trap nothin'
int lowBar = Math.min(left[i - 1], right[i + 1]);
if (lowBar > A[i])
res += lowBar - A[i];
}
return res;
}
Lexi's Leetcode solutions 