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);
maxArea = max(area,maxArea);
}
else
{
area = height[i];
maxArea = max(area,maxArea);
break;
}
j++;
}
}
return maxArea;
}
不超时的
int largestRectangleArea(vector &height) {
stack st;
height.push_back(0);
int maxArea=0;
int area=0;
int n = height.size();
for (int i=0; i
{
if (st.empty()||height[i]>height[st.top()])
{
st.push(i++);
}
else
{
int tmp = st.top();
st.pop();
if (st.empty())
area = height[tmp]*i;
else
area = height[tmp]*(i-st.top()-1);
maxArea = max(area,maxArea);
}
}
return maxArea;
} | p********n
发帖数: 165 | |
|
