# What is the best run-time for this problem?

• What is the best run-time for this problem?

• Here is my solution. It is AC and straightforward. There are steps to improve though. What do you think?

``````public class Solution {
int max = 0;
int [] h;
class WorkItem {
int from, to, level;
WorkItem(int from, int to, int level) {
this.from = from; this.to = to; this.level = level;
}
}

public int largestRectangleArea(int[] height) {
max = 0;
if (height == null || height.length == 0) return 0;
if (height.length == 1) return height[0];
this.h = height;
int level = 1;
items.clear();
for (int i = 0; i < height.length; i++) {
level = Math.min(level, height[i]);
}
WorkItem next;
while ((next = items.pollFirst()) != null) {
process(next.from, next.to, next.level);
}
return max;
}

private void process(int start, int end, int level) {
if (start >= end) return;
if (start == end - 1 && h[start] > 0) {
max = Math.max(max, h[start]);
return;
}
int nextLevel = Integer.MAX_VALUE;
for (int i = start; i < end; i++) {
if (h[i] < level) {
items.addLast(new WorkItem(i + 1, end, level));
return;
} else {
if (h[i] > level) {
nextLevel = Math.min(nextLevel, h[i]);
}
}
}
max = Math.max(max, level * (end - start));
if (nextLevel > level && nextLevel <= Integer.MAX_VALUE) {
}
}
}``````

• ``````According the GeeksForGeeks's idea, two different implementation, both are O(n) time complexity

int largestRectangleArea(vector<int> &height) {
// push a sentinel node back into the end of height
// to make the code logic more concise
height.push_back(0);
stack<int> s;
int ret = 0, h = 0, w = 0;
int i = 0, n = height.size();

while (i < n) {
if (s.empty() || height[s.top()] <= height[i])
s.push(i++);
else {
h = height[s.top()];
s.pop();
w = s.empty() ? i : i - s.top() - 1;
if (h * w > ret) ret = h * w;
}
}

return ret;
}

// all the nodes just push in and pop out once
// time complexity is O(2n)
int largestRectangleArea1(vector<int> &height) {
int ret = 0;
height.push_back(0);
vector<int> index;

int h = 0, w = 0;
for(int i = 0; i < height.size(); i++) {
while(index.size() > 0 && height[index.back()] >= height[i]) {
h = height[index.back()];
index.pop_back();

w = index.size() > 0 ? i - index.back() - 1 : i;
if(h * w > ret) ret = h * w;
}

index.push_back(i);
}

return ret;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.