A*******e
发帖数: 2419 | 1 写了个O(n^2)的算法，从中心向两侧展开，超时了。
另外这题为何叫Container With Most Water？明明是max histogram area嘛。函数接
口也叫maxArea，跟容器、水有何关系？ | j********g
发帖数: 80 | 2 俩指针 头一个 尾一个 扫一遍 O(N)不就解决了么
【在 A*******e 的大作中提到】
: 写了个O(n^2)的算法，从中心向两侧展开，超时了。
: 另外这题为何叫Container With Most Water？明明是max histogram area嘛。函数接
: 口也叫maxArea，跟容器、水有何关系？
| A*******e
发帖数: 2419 | 3 谢谢提醒。是我看错了。这个和max histogram area不一样。
写了一个，是不是有点长？谁有更简洁的写法？
class Solution {
public:
int maxArea(vector& height) {
int head = 0;
int tail = height.size() - 1;
int result = GetArea(height, head, tail);
while (head < tail) {
if (height[head] < height[tail]) {
int next_head = head + 1;
while (next_head < height.size() &&
height[next_head] <= height[head]) {
++next_head;
}
head = next_head;
} else {
int next_tail = tail - 1;
while (next_tail >= 0 && height[next_tail] <= height[tail]) {
--next_tail;
}
tail = next_tail;
}
result = max(result, GetArea(height, head, tail));
}
return result;
}
private:
int GetArea(const vector& height, int head, int tail) {
return head < tail ? (tail - head) * min(height[head], height[tail])
: 0;
}
};
【在 j********g 的大作中提到】
: 俩指针 头一个 尾一个 扫一遍 O(N)不就解决了么
|
|
