|
|---|
|
|
|
|
|
|
b**m
发帖数: 1466 | 1 没想出用stack方法，我这个也是O(n)吧？
public class Solution {
public int largestRectangleArea(int[] height) {
if(height.length ==0 ){
return 0;
}
int[] left= new int[height.length]; // width on its left side(and
itself)
int[] right= new int[height.length]; // width on its right side(and
itself)
left[0] = 1;
right[right.length-1] = 1;
for(int i=1;i< height.length; i++){
if(height[i]> height[i-1]){
left[i] = 1;
}else if(height[i] == height[i-1]){
left[i] = left[i-1] +1;
}else{
left[i] = 1;
int j = i-1;
while(j>=0 && height[i] <= height[j]){
left[i] += left[j];
j-= left[j]; //jump
}
}
}
for(int i = right.length -2;i>=0;i--){
if(height[i]>height[i+1]){
right[i] = 1;
}else if(height[i] == height[i+1]){
right[i] = right[i+1] +1;
}else{
right[i] = 1;
int j = i+1;
while(j < right.length && height[i] <= height[j]){
right[i] += right[j];
j+= right[j]; //jump
}
}
}
int max = 0;
for(int i=0;i
int area = (left[i] + right[i] -1) *height[i];
if(area> max){
max = area;
}
}
return max;
}
} | b********g
发帖数: 28 | 2 public class Solution {
public int largestRectangleArea(int[] height) {
// Start typing your Java solution below
// DO NOT write main() function
if(height == null || height.length == 0) return 0;
int n = height.length;
int[] left = new int[n];
Stack stack = new Stack();
int max = 0;
for(int i = 0; i < n; i++){
if(stack.empty() || height[stack.peek()] <= height[i]){
left[i] = i;
stack.push(i);
}else{
while(!stack.empty() && height[stack.peek()] > height[i]){
int idx = stack.pop();
left[i] = left[idx];
max = Math.max(max, height[idx] * (i - left[idx]));
}
stack.push(i);
}
}
while(!stack.empty()){
int idx = stack.pop();
max = Math.max(max, height[idx] * (n - left[idx]));
}
return max;
}
} |
|
|
|
|
|
|
