a***e
发帖数: 413 | 1 看着很容易，一写bruteforce的就TLE，后来看了idea是用stack，如下。
TLE的是O(N^2),用stack是因为每个元素只入栈出栈一次push 和pop都是O（1），所以
是O(N)是吧？一犯困就很糊涂。轻拍
int largestRectangleArea(vector &height) {
int maxArea=0;
int area=0;
int n = height.size();
if (n==1)
return height[0];
int j;
for (int i=0; i
{
j=i+1;
while(j
{
if (height[j]>=height[i])
{
area = height[i]*(j-i+1);
... 阅读全帖 |
|
n****r
发帖数: 120 | 2 可以过
public class Solution {
public static class Bar{
int height, startIdx;
Bar(int h, int i){ height = h; startIdx = i; }
}
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) return 0;
int n = matrix.length, m = matrix[0].length;
int[][] aux = new int[n][m];
for (int i=0; i
aux[0][i] = matrix[0][i] - '0';
}
for (int i=1; i
... 阅读全帖 |
|
c**********e
发帖数: 2007 | 3 这是改过的。过了所有测试。复杂度O（n）。
#include
using namespace std;
inline int min(int a, int b) { return a < b ? a : b; }
int maxArea(int a[], int size) {
int mArea=0, area, left=0, right=size-1;
while(left
area=(right-left) * min(a[left],a[right]);
if(area>mArea) mArea=area;
if(a[left]<=a[right]) {
int i=left;
while(i
left=i;
} else {
int j=right;
while(j>left && a[j]<=a[right]) j--;
right=j;
}
}
... 阅读全帖 |
|
c**********e
发帖数: 2007 | 4 这是改过的。过了所有测试。复杂度O（n）。
#include
using namespace std;
inline int min(int a, int b) { return a < b ? a : b; }
int maxArea(int a[], int size) {
int mArea=0, area, left=0, right=size-1;
while(left
area=(right-left) * min(a[left],a[right]);
if(area>mArea) mArea=area;
if(a[left]<=a[right]) {
int i=left;
while(i
left=i;
} else {
int j=right;
while(j>left && a[j]<=a[right]) j--;
right=j;
}
}
... 阅读全帖 |
|
g**e
发帖数: 6127 | 5 激动啊，得到大牛肯定
不过你前面提到的"c(x)=在x左边最后一个比ax小的位置 c(x)=0 if all are larger
than ax"，我觉得这种情况c(x)=-1
这样后面算最大面积的时候 (b(x)-c(x)-1)*a(x)才正确
比如a={2,3}, b={2,2}, c={-1,0} 最大面积4
贴个完整的代码
public class LargestHistogramRectangleDP {
public static int largestHistogram(int[] a) {
int maxArea = 0;
int n = a.length;
int[] b = new int[n];
int[] c = new int[n];
b[n-1] = n;
fo... 阅读全帖 |
|
d*****d
发帖数: 180 | 6 sorry for laziness, too many typos in previous code. this one has been
tested
int[] a={1,2,3,4};
int l=1,r=a.length-1;
int maxArea=0;
while(l
{
int d=a[r]-a[l];
int temp=(r-l)*(d>0 ? a[l]:a[r]);
maxArea=maxArea>temp ? maxArea:temp;
if (d>0)
l++;
else
r--;
}
System.out.println("max="+maxArea); |
|
d*****d
发帖数: 180 | 7 sorry for laziness, too many typos in previous code. this one has been
tested
int[] a={1,2,3,4};
int l=1,r=a.length-1;
int maxArea=0;
while(l
{
int d=a[r]-a[l];
int temp=(r-l)*(d>0 ? a[l]:a[r]);
maxArea=maxArea>temp ? maxArea:temp;
if (d>0)
l++;
else
r--;
}
System.out.println("max="+maxArea); |
|
s******e
发帖数: 108 | 8 another version of code. O(n)
public int maxArea(int[] a) {
int maxArea =0;
int left =0;
int right =a.length-1;
int area =0;
while(left
area = Math.min(a[left], a[right]) *(right-left);
if(area>maxArea)
maxArea = area;
if(a[left]<= a[right])
left++;
else
right--;
}
return maxArea;
} |
|
S**I
发帖数: 15689 | 9 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
S**I
发帖数: 15689 | 10 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
h*****y
发帖数: 218 | 11 在网上发现这个最大直方图求面积的题目的解答，有一个地方没看明白
http://www.sureinterview.com/shwqst/1117001
下面这个代码的stack为什么有一个get的方法？
if (prev.height > stk.get(stk.size() - 2).height) {
======================================================================
public long getMaxArea(int[] histogram) {
long maxArea = 0;
if (histogram == null || histogram.length == 0)
return maxArea;
Stack- stk = new Stack
- ();
stk.push(new Item(Integer.MIN_VALUE, -1));
for (int i = 0; i <... 阅读全帖 |
|
a***e
发帖数: 413 | 12 这样是不是 O(N^N)的复杂度?
class Solution {
public:
int maximalRectangle(vector > &matrix) {
int row=matrix.size();
if (row==0) return 0;
int col=matrix[0].size();
if (col==0) return 0;
//find all disjoint rectangles
vector> flag(row, vector(col,false));
int maxArea=INT_MIN;
for (int r=0; r
for (int c=0; c
{
int area=0;
if (matrix[... 阅读全帖 |
|
s*******r
发帖数: 2697 | 13 sln 1: brute force
calculate cost for every possible rectangle and return the maximum rectangle
within budget.
complexity: O(n^6)
O(n^4) rectangles and calc cost for each rectangle is O(n^2)
sln2: O(n^4)
1)fix left and right column of matrix (O(n^2) possibilities)
2)for each fixed left and right column
a)for each row, calc the cost from left to right, as tmp[i] O(n^2)
b)given 1D array tmp[], find the longest sub-array within budget, can be
done in O(n)
complexity: O(n^4)
sln3: O(n^3)
in sl... 阅读全帖 |
|
B*M
发帖数: 1340 | 14 大家看看这个怎么样？
double maxArea(double a[], int size){
int left = 0;
int right = size - 1;
double area = min(a[left], a[right]) * (right - left);
while(left < right){
double temp = min(a[left], a[right]) * (right - left);
area = temp > area ? temp :area;
if(a[left] < a[right]){
double t = a[left];
while(a[left] <= t && left < right){
left ++;
}
} else {
double t = a [right];
whi... 阅读全帖 |
|
c**********e
发帖数: 2007 | 15 You guys have made the algorithm clear. Let me write the code.
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
int maxArea(int a[], int size) {
int mArea=0, area, left=0, right=size-1;
while(left
area=(right-left) * min(a[left],a[right]);
if(area>mArea) mArea=area;
int i=left, j=right;
while(i < right && a[i] <= a[left]) i++;
while(j > left && a[j] <= a[right]) j--;
if(a[left]<=a[right]) left=i;
... 阅读全帖 |
|
i**********e
发帖数: 1145 | 16 There is a flaw in the logic:
Consider this case [1,2,4,3]
In the first iteration, d=3-1=2. Since d > 0, you will decrement r by one.
But the maximum is by choosing l=1 and r=3, which has maxArea of 4, so you'
ve essentially did not consider some cases. |
|
c**********e
发帖数: 2007 | 17
测试结果：
Run Status: Accepted!
Progress: 12/12 test cases passed.
代码：
class Solution {
public:
int maxArea(vector height) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size=height.size();
int mArea=0, area, left=0, right=size-1;
while(left
area=(right-left) * min(height[left],height[right]);
if(area>mArea) mArea=area;
if(height[left]<=height[right]) {
... 阅读全帖 |
|
i**********e
发帖数: 1145 | 18 Good, this works.
My code is below for reference.
int maxArea(vector height) {
int n = height.size();
int L = 0, R = n-1;
int largestArea = 0;
while (L < R) {
int lHeight = height[L], rHeight = height[R];
int area = min(lHeight, rHeight) * (R - L);
if (area > largestArea)
largestArea = area;
if (lHeight <= rHeight)
while(L < R && height[L] <= lHeight) L++;
if (lHeight >= rHeight)
while (L < R ... 阅读全帖 |
|
c**********e
发帖数: 2007 | 19 You guys have made the algorithm clear. Let me write the code.
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
int maxArea(int a[], int size) {
int mArea=0, area, left=0, right=size-1;
while(left
area=(right-left) * min(a[left],a[right]);
if(area>mArea) mArea=area;
int i=left, j=right;
while(i < right && a[i] <= a[left]) i++;
while(j > left && a[j] <= a[right]) j--;
if(a[left]<=a[right]) left=i;
... 阅读全帖 |
|
i**********e
发帖数: 1145 | 20 There is a flaw in the logic:
Consider this case [1,2,4,3]
In the first iteration, d=3-1=2. Since d > 0, you will decrement r by one.
But the maximum is by choosing l=1 and r=3, which has maxArea of 4, so you'
ve essentially did not consider some cases. |
|
c**********e
发帖数: 2007 | 21
测试结果：
Run Status: Accepted!
Progress: 12/12 test cases passed.
代码：
class Solution {
public:
int maxArea(vector height) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size=height.size();
int mArea=0, area, left=0, right=size-1;
while(left
area=(right-left) * min(height[left],height[right]);
if(area>mArea) mArea=area;
if(height[left]<=height[right]) {
... 阅读全帖 |
|
i**********e
发帖数: 1145 | 22 Good, this works.
My code is below for reference.
int maxArea(vector height) {
int n = height.size();
int L = 0, R = n-1;
int largestArea = 0;
while (L < R) {
int lHeight = height[L], rHeight = height[R];
int area = min(lHeight, rHeight) * (R - L);
if (area > largestArea)
largestArea = area;
if (lHeight <= rHeight)
while(L < R && height[L] <= lHeight) L++;
if (lHeight >= rHeight)
while (L < R ... 阅读全帖 |
|
h****n
发帖数: 1093 | 23 不管是哪个题，都可以O（n） 贴下我的代码：
Container with most water：
class Solution {
public:
int maxArea(vector &height) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int i = 0;
int j = height.size()-1;
int res = INT_MIN;
while(i
{
int minHeight = height[i]>=height[j]?height[j]:height[i];
int area = (j-i)*minHeight;
if(area >= res) res = area;
if... 阅读全帖 |
|
A*******e
发帖数: 2419 | 24 写了个O(n^2)的算法，从中心向两侧展开，超时了。
另外这题为何叫Container With Most Water？明明是max histogram area嘛。函数接
口也叫maxArea，跟容器、水有何关系？ |
|
A*******e
发帖数: 2419 | 25 谢谢提醒。是我看错了。这个和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;
... 阅读全帖 |
|
